IE interfaces (산업공학)

Korean Institute of Industrial Engineers (대한산업공학회)
권호 표지

Development of a Planning System for the Routing and Scheduling of Vehicles in Pickup and Delivery Services

수배송 서비스를 위한 운송계획 최적화 시스템 개발

  • Choi, Ji-Young (Logistics Technology Research Team, Electronics and Telecommunications Research Institute) ;
  • Lee, Tae-Han (Department of Industrial and Information Systems Engineering, Chonbuk National University) ;
  • Lim, Jae-Min (Logistics Technology Research Team, Electronics and Telecommunications Research Institute)
  • 최지영 (한국전자통신연구원 물류기술팀) ;
  • 이태한 (전북대학교 산업정보시스템공학과, 공업기술연구센터) ;
  • 임재민 (한국전자통신연구원 물류기술팀)
  • Received : 20060300
  • Accepted : 20060600
  • Published : 2006.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we develop a planning system for the routing and scheduling of vehicles in pickup and delivery service such as door-to-door parcel service. Efficient routing and scheduling of vehicles is very important in pickup and delivery service. The routing and scheduling problem is a variation of vehicle routing problem which has various realistic constraints. We develop a heuristic algorithm based on tabu search to solve the routing and scheduling problem. We develop a routing and scheduling system installed the algorithm as a planning engine. The system manage the basic data and uses GIS data to make a realistic route plan.

Keywords

References

  1. Brandao, J. and Mercer, A.(1998), The multi-trip vehicle routing and problem. Journal of the Operational Research Society, 49, 799-805 https://doi.org/10.1057/palgrave.jors.2600595
  2. Cao, B., Sun, M., and Macleod, C(1999), Applying GIS and combinatorial optimization to fiber deployment plans.Journal of Heuristics , 5, 385-402 https://doi.org/10.1023/A:1009628321600
  3. Chao, I. M., Golden, B. L., and Wasil, E. A.(1993), A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Science, 13, 371-406
  4. Christofides, N. and Eilon, S.(1969), An algorithm for the vehicle-dispatching problem. Operations Research, 20, 309-318 https://doi.org/10.1057/jors.1969.75
  5. Christofides, N., Mingozzi, A., and Toth, P.(1979), The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., and Sandi, C. (Eds.), Combinatorial Optimization, Wiley, Chichester
  6. Chung E- Y. and Park Y-B.(2004), A Genetic Algorithm for Vehicle Routing Problems With Mixed Delivery and Pick-up, Journal of the Korean Institute of Industrial Engineers, 30, 346-354
  7. Clarke, G. and Wright,J. W.(1964), Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581 https://doi.org/10.1287/opre.12.4.568
  8. Cordeau,J. -F., Gendreau, M., and Laporte, G.(1997), A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks. 30, 105-119 https://doi.org/10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
  9. Derekenaris, G., Garofalakis, J., Makris, C., Prentzas, J., Sioutas, S., and Tsakalidis, A.(2001), Integrating GIS, GPS and GSM technologies for the effective management of ambulances. Computers. Environment and Urban Systems. 25. 267-278 https://doi.org/10.1016/S0198-9715(00)00025-9
  10. Goetschalckx, M. and Jacobs-Blecha, C.(1989), The vehicle routing problem with backhauls. European Journal of Operational Research, 42, 39-51 https://doi.org/10.1016/0377-2217(89)90057-X
  11. Hong S-C. and Park Y-B.(2004), A Two-phase Method tor the Vehicle Routing Problems with Time Windows, IE Interfaces, 17, 103-110
  12. Jeon,D.(2002), A heuristic algorithm for the vehicle rouring problem with time-dependent travel time. MS thesis, Daejeon, KAIST
  13. Kim Y-H., Jang Y-S., and Ryu H-J.(2002), A Study on Developing Vehicle Scheduling System using Constraint Programming and Metaheucistics, Proceedings of the IE & MS 2002 Couference, 979-986
  14. Marcello, S. and Toth, P.(1990), Knapsack Problems. Wiley, Chichester
  15. Mosheiov, G.(1998), Vehicle routing with pick-up and delivery: tour-partitioning heuristics. Computers and industrial Engineering, 34, 669-684 https://doi.org/10.1016/S0360-8352(97)00275-1
  16. Nanry, W. P. and Barnes,J. W.(2000), Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Research Part B-Methodological, 34, 107-121 https://doi.org/10.1016/S0191-2615(99)00016-8
  17. Osman,I. H.(1993), Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, 421-451 https://doi.org/10.1007/BF02023004
  18. Renaud,J., Boctor, F. F., and Laporte, G.(1996), An improved petalheuristic for the vehicle routing problem.Journal of the Operational Research Society, 47, 329-336 https://doi.org/10.1057/jors.1996.29
  19. Renaud,J., Laporte, G., and Boctor, F. F.(1996),. A tabu search heuristic for the multi-depot vehicle routing problem. Computers and Operations Research, 23, 229-235 https://doi.org/10.1016/0305-0548(95)O0026-P
  20. Solomon, M. M.(1987),. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35, 254-265 https://doi.org/10.1287/opre.35.2.254
  21. Taillard, E. D., Laporte, G. and Gendreau, M.(1996), Vehicle routing with multiple use of vehicles. Journal of the Operational Research Society, 47, 1065-1070 https://doi.org/10.1057/jors.1996.133
  22. Thangiah, S. R., Porvin,J. Y., and Sun. T.(1996), Heuristic approaches to vehicle routing with backhauls and time windows. Computers and Operations Research, 23, 1043-1057 https://doi.org/10.1016/0305-0548(96)00018-4
  23. Toth, P. and Vigo,D.(1999), A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113,528-543 https://doi.org/10.1016/S0377-2217(98)00086-1
  24. Toth, P. and Vigo, D.(2003), The Granular Tabu Search and Its Application to the Vchicle-Routing Problem. INFORMS journal on computing, 15, 333-346 https://doi.org/10.1287/ijoc.15.4.333.24890