Journal of Korean Society of Industrial and Systems Engineering (산업경영시스템학회지)

Society of Korea Industrial and System Engineering (한국산업경영시스템학회)
권호 표지

A Two-Stage Heuristic for Period Vehicle Routing : Minimizing the Fleet Size

소요차량을 최소화하는 기간차량경로 문제에 관한 2단계 발견적 기법

  • Published : 2008.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

기간차량경로 문제는 차량용량제약을 고려한 차량경로문제를 다 기간으로 확장한 형태의 문제로 역방향 로지스틱스의 폐기물 혹은 재활용품 수거에 관련된 주요한 운영 문제들 중의 하나로 각 고객에 대해서는 계획기간 중에 방문해야 하는 횟수가 정해져 있어 방문날짜 조합을 결정해야 하며 주어진 방문날짜 조합 하에 각 기간의 차량경로도 결정해야 한다. 주요한 제약조건으로는 차량의 용량제약과 각 기간의 가용 시간제약이 있으며 소요차량의 대수를 최소화하는 것을 목적으로 한다. 본 연구에서는 대상 문제의 복잡도로 인하여 초기해를 구하고 그 해를 개선하는 2 단계 발견적 알고리듬을 제안하였으며 다양한 문제들에 대한 계산실험 결과 본 연구에서 제안하고 있는 발견적 알고리듬이 기존 알고리듬보다 우수함을 보였다.

Keywords

References

  1. Angelelli, E. and Speranza, M. G.; "The periodic vehicle routing problem with intermediated facilities," European Journal of Operational Research, 137：233-247, 2002 https://doi.org/10.1016/S0377-2217(01)00206-5
  2. Baptisa, S., Oliveira, R. C., and Zúquete, E.; "A period vhicle routing case study," European Journal of Operational Research, 139：220-229, 2002 https://doi.org/10.1016/S0377-2217(01)00363-0
  3. Beltrami, E. and Bodin, L.; "Networks and vehicle routing for municipal waste collection," Networks, 4：65-94, 1974 https://doi.org/10.1002/net.3230040106
  4. Bertazzi, L., Paletta, G., and Speranza, M. G.; "An improved heuristic for the period traveling salesman problem," Computers and Operations Research, 31：1215-1222, 2004 https://doi.org/10.1016/S0305-0548(03)00075-3
  5. Bloemhof-Ruwaard, J. M., Fleschmann, M., and van Nunen, J. A. E. E.; "Reviewing distribution issues in reverse logistics," Lecture Note in Economics and Mathematical Systems, 480：23-44, 1999
  6. Bommisetty, D. and Dessouky, M.; "Scheduling collection of recyclable material at Northern Illinois University campus using a two-phase algorithm," Computes and Industrial Engineering, 35：435-438, 1998 https://doi.org/10.1016/S0360-8352(98)00127-2
  7. Campbell, A. M. and Hardin, J. R.; "Vehicle minimization for periodic deliveries," European Journal of Operational Research, 165：668-684, 2005 https://doi.org/10.1016/j.ejor.2003.09.036
  8. Chao, I.-M., Golden, B. L., and Wasil, E.; "A new heuristic for the period traveling salesman problem," Computers and Operations Research, 22：553-565, 1995 https://doi.org/10.1016/0305-0548(94)00031-3
  9. Christofides, N. and Beasley, J.; "The period routing problem," Networks, 14：237-256, 1984 https://doi.org/10.1002/net.3230140205
  10. Claassen, G. D. H. and Hendriks, Th. H. B.; "An application of special ordered sets to a periodic milk collection problem," European Journal of Operational Research, 180：754-769, 2007 https://doi.org/10.1016/j.ejor.2006.03.042
  11. Cordeau, J.-F., Gendreau, M., and Laporte, G.; "A tabu search heuristic for periodic and multi-depot vehicle routing problems," Networks, 30：109-124, 1997
  12. Fisher, M. L. and Jailumar, R.; "A generalized assignment for vehicle routing," Networks, 11：109-124, 1981 https://doi.org/10.1002/net.3230110205
  13. Fleischmann, M., Bloemhof-Ruwaard, J. M., Dekker, R., van der Laan, E., van Nunen, J. A. E. E., and van Wassenhove, L. N.; "Quantitative models for reverse logistics：a review," European Journal of Operational Research, 103：1-17, 1997 https://doi.org/10.1016/S0377-2217(97)00230-0
  14. Francis, P. and Smilowitz, K.; "Modeling techniques for periodic vehicle routing problems," Transportation Research Part B：Methodological, 40：872-884, 2006 https://doi.org/10.1016/j.trb.2005.12.001
  15. Gaudioso, M. and Paletta, G.; "A heuristic for the periodic vehicle routing problem," Transportation Science, 26：86-92, 1992 https://doi.org/10.1287/trsc.26.2.86
  16. Paletta, G.; "A multi-period traveling salesman proble m：heuristic algorithms," Computers and Operations Research, 19：789-795, 1992 https://doi.org/10.1016/0305-0548(92)90018-Z
  17. Paletta, G. and Triki, C.; "Solving the asymmetric traveling salesman problem with periodic constraints," Networks, 44：31-37, 2004 https://doi.org/10.1002/net.20011
  18. Russell, R. A. and Gribbin, D.; "A multiphase approach to the period routing problem," Networks, 21： 747-765, 1991 https://doi.org/10.1002/net.3230210704
  19. Russell, R. A. and Igo, W.; "An assignment routing problem," Networks, 9：1-17, 1979 https://doi.org/10.1002/net.3230090102
  20. Tan, C. C. and Beasley, J. E.; "A heuristic algorithm for the periodic vehicle routing problem," Omega, 12： 497-504, 1984 https://doi.org/10.1016/0305-0483(84)90050-1
  21. Teixeira, J., Antunes, A. P., and Sousa, J. P.; "Recyclable waste collection planning," European Journal of Operational Research, 158：543-554, 2004 https://doi.org/10.1016/S0377-2217(03)00379-5