Abstract
In this paper, we introduce a multi vehicle version of the Time-Dependent Prize-
Collecting Arc Routing Problem (TD-MPARP). It is inspired by a situation
where a transport manager has to choose between a number of full truck load
pick-ups and deliveries to be performed by a fleet of vehicles. Real-life traffic
situations where the travel times change with the time of day are taken into
account.
Two metaheuristic algorithms, one based on Variable Neighborhood Search and
one based on Tabu Search, are proposed and tested for a set of benchmark
problems, generated from real road networks and travel time information. Both
algorithms are capable of finding good solutions, though the Tabu Search approach
generally shows better performance for large instances whereas the VNS
is superior for small instances. We discuss the structural differences of the
implementation of the algorithms which explain these results.
Collecting Arc Routing Problem (TD-MPARP). It is inspired by a situation
where a transport manager has to choose between a number of full truck load
pick-ups and deliveries to be performed by a fleet of vehicles. Real-life traffic
situations where the travel times change with the time of day are taken into
account.
Two metaheuristic algorithms, one based on Variable Neighborhood Search and
one based on Tabu Search, are proposed and tested for a set of benchmark
problems, generated from real road networks and travel time information. Both
algorithms are capable of finding good solutions, though the Tabu Search approach
generally shows better performance for large instances whereas the VNS
is superior for small instances. We discuss the structural differences of the
implementation of the algorithms which explain these results.
| Original language | English |
|---|---|
| Publication status | Published - 2015 |