CONSTRUCTING INITIAL SOLUTIONS FOR VEHICLE ROUTING PROBLEM WITH PICKUP AND DELIVERY
Keywords:
vehicle routing problem, mathematical model, optimization, initial solution, clusterization
Abstract
In this paper we look at Vehicle Routing Problem with Pickup and Delivery. Problem description and mathematical model were presented. The two-stage initial solution construction algorithm was proposed. The algorithm was tested on the known benchmarks and shown better performance compared with known methods.
References
Dantzig, A. G. B., Ramser, J. H. The Truck Dispatching Problem Stable // Management Science. – 1959. – 6 (1). – Р. 80-91.
P. Toth, D. Vigo, The vehicle routing problem // Society for Industrial Mathematics, 2002. – Vol. 9
Eksioglu, B., Vural, A. V., & Reisman, A. The vehicle routing problem: A taxonomic review // Computers & Industrial Engineering. – 2009. – 57 (4). – Р. 1472-1483.
Savelsbergh, M. W. P., Sol, M. The General Pickup and Delivery Problem // Transportation Science. – 1995. – 29 (1). – Р. 17-29.
Li, H., Lim, A. A Metaheuristic for Pickup and Delivery Problem with Time Windows. In: Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence. Dallas, TX, USA, 2001. – Р. 160-167.
Solomon, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints // Operations Research. – 1987. – 5 (2). – Рр. 254-265.
Bent, R., Hentenryck, P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows // Computers & Operations Research. – 2006. – 33 (4). – Р. 875-893.
Ropke, S., Pisinger, D. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows // Transportation Science. – 2006. – 40 (4). – Рр. 455-472.
M. I. Hosny and C. L. Mumford. Investigating genetic algorithms for solving the multiple vehicle pickup and delivery problem with time windows. In MIC2009 // Metaheuristic International Conference, July 2009.
Hosny, M. I., Mumford, C. L. Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows // Journal of King Saud University, 2011.
Ropke, S., Laporte, G., Cordeau, J.-F. Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows // Networks. – 2007, 49 (4). – Р. 258-272.
Holborn, P. L., Thompson, J. M., Lewis, R. Combining Heuristic and Exact Methods to Solve the Vehicle Routing Problem with Pickups and Deliveries and Time Windows, In: Proceedings of the main European events on Evolutionary Computation. – Malaga, Spain,
2012. – Р. 63-74.
Ropke, S., Pisinger, D. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows // Transportation Science. – 2006. – 40 (4). – Р. 455-472.
Hathaway, R. J., Bezdek, J. C., Davenport, J. W. (1996). On relational data versions of c-means algorithms // Pattern Recognition Letters, 5 (96). – Рр. 607-612.
Lu, Q., Dessouky, M. M. A New Insertion-based Construction Heuristic for Solving the Pickup and Delivery Problem with Time Windows // European Journal of Operational Research. – 2006. – 175 (2). – Р. 672-687.
P. Toth, D. Vigo, The vehicle routing problem // Society for Industrial Mathematics, 2002. – Vol. 9
Eksioglu, B., Vural, A. V., & Reisman, A. The vehicle routing problem: A taxonomic review // Computers & Industrial Engineering. – 2009. – 57 (4). – Р. 1472-1483.
Savelsbergh, M. W. P., Sol, M. The General Pickup and Delivery Problem // Transportation Science. – 1995. – 29 (1). – Р. 17-29.
Li, H., Lim, A. A Metaheuristic for Pickup and Delivery Problem with Time Windows. In: Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence. Dallas, TX, USA, 2001. – Р. 160-167.
Solomon, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints // Operations Research. – 1987. – 5 (2). – Рр. 254-265.
Bent, R., Hentenryck, P. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows // Computers & Operations Research. – 2006. – 33 (4). – Р. 875-893.
Ropke, S., Pisinger, D. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows // Transportation Science. – 2006. – 40 (4). – Рр. 455-472.
M. I. Hosny and C. L. Mumford. Investigating genetic algorithms for solving the multiple vehicle pickup and delivery problem with time windows. In MIC2009 // Metaheuristic International Conference, July 2009.
Hosny, M. I., Mumford, C. L. Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows // Journal of King Saud University, 2011.
Ropke, S., Laporte, G., Cordeau, J.-F. Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows // Networks. – 2007, 49 (4). – Р. 258-272.
Holborn, P. L., Thompson, J. M., Lewis, R. Combining Heuristic and Exact Methods to Solve the Vehicle Routing Problem with Pickups and Deliveries and Time Windows, In: Proceedings of the main European events on Evolutionary Computation. – Malaga, Spain,
2012. – Р. 63-74.
Ropke, S., Pisinger, D. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows // Transportation Science. – 2006. – 40 (4). – Р. 455-472.
Hathaway, R. J., Bezdek, J. C., Davenport, J. W. (1996). On relational data versions of c-means algorithms // Pattern Recognition Letters, 5 (96). – Рр. 607-612.
Lu, Q., Dessouky, M. M. A New Insertion-based Construction Heuristic for Solving the Pickup and Delivery Problem with Time Windows // European Journal of Operational Research. – 2006. – 175 (2). – Р. 672-687.
Published
2012-11-26
Section
Статті
