ПОБУДОВА ПОЧАТКОВОГО РІШЕННЯ ДЛЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТНИХ ЗАСОБІВ З ПІДБОРОМ ТА ДОСТАВКОЮ
Ключові слова:
маршрутизація транспортних засобів, математична модель, оптимізація, початкове рішення, кластеризація
Анотація
В роботі розглянута задача маршрутизації транспортних засобів з підбором та доставкою (Vehicle Routing Problem with Pickup and Delivery – VRPPD). Ця задача є варіантом окремої задачі маршрутизації транспортних засобів (VRP). Наведено формулювання задачі та її математична модель. Запропоновано двоступеневий алгоритм побудови початкового рішення для даної задачі. Результати експериментів на відомих еталонних прикладах порівняно з найкращими відомими на даний момент. Отримані результати є кращими у порівнянні із відомими результатами побудови початкового рішення для VRPPD.
Посилання
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.
Опубліковано
2012-11-26
Розділ
Статті
