Back to Search
Start Over
Integration of a robust shortest path algorithm with a time dependent vehicle routing model and applications
- Publication Year :
- 2003
- Publisher :
- IEEE Computer Society, 2003.
-
Abstract
- This paper describes a way of combining two techniques, in order to define a framework that can deal with the following problem: find an optimized set of routes when the customers set is a proper subset of an entire network, and variable traffic conditions have to be taken into account. This is accomplished on one hand by extending the vehicle routing problem (VRP) to a time dependent case (TDVRP), on the other hand by using an appropriate algorithm, the robust shortest path (RPS) that can provide itineraries when moving to a location to another, and guarantee good performance under any possible road network situation. Once a proper description of the TDVRP model is given, we discuss the optimization technique, based on the ant colony system (ACS), and the robust shortest path (RPS) algorithm. Different ways of integrating these techniques are discussed The one presented here consists in using the RPS algorithm for the calculation of the paths among each pair of customers, so that this information can to be used by the TDVRP optimization in a very efficient way. In the case of a real road network, some tests have been made, that show that the optimal solutions obtained for the classic VRP case are sub optimal when considered in a time dependent context, revealing that the approximation of constant speeds is sometimes inadequate.
- Subjects :
- Set (abstract data type)
Mathematical optimization
Computer science
Vehicle routing problem
Shortest path problem
Context (language use)
Directed graph
K shortest path routing
Ant colony
Dijkstra's algorithm
Ant colony optimization
Cellular neural networks
Heuristic algorithms
Joining processes
Logistics
Roads
Robustness
Routing
Vehicles
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....7ddafa7520ff659234272ad5f19162c7