Hybrid 유전자 알고리즘을 이용한 서비스 가능 시간대가 존재하는 차량경로문제 = A Hybrid Genetic Algorithm for Vehicle Routing Problem with Possible Service Time Windows

다국어 초록 (Multilingual Abstract)

The main purpose of this study is to find out the shortest path(minimize total travel distance) of the vehicle routing problem with possible service time windows. This study suggests a mathematical programming model and verifies the suggested mathematical programming model by using CPLEX 11.1. This study also suggests a hybrid genetic algorithm which considers the generation for an initial solution by random and saving algorithm, the process of solution improvement by 2-Opt. The suggested algorithm is compared by Solomon`s examples considering possible service time windows. We found the better solutions concerning total travel distance rather than best-known solutions in R/RC-type Solomon`s examples.

참고문헌 (Reference)

1 Liong, C. Y, "Vehicle Routing Problem: Models and Solutions" 4 (4): 205-218, 2008

2 Brӓysy, O, "Vehicle Routing Problem with Time Windows, Part Ⅱ: Metaheuristics" 39 (39): 119-139, 2005

3 Homberger, J, "Two Evolutionary Metaheuristics for the Vehicle Routing Problems with Time Windows" 37 (37): 297-318, 1999

4 Desrosiers, J., "Time Constrained Routing and Scheduling, In: Handbooks in Operations Research and Management Science, Network Routing" North-Holland 35-139, 1995

5 Laporte, G., "The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms" 59 (59): 345-358, 1992

6 Cordeau, J. F., "The VRP with Time Windows, In: The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics" Philadelphia 157-193, 2002

7 Dantzig, G. B, "The Truck Dispatching Problem" 6 (6): 80-91, 1959

8 Chiang, W. C, "Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows" 63 (63): 3-27, 1996

9 Clark, G, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" 12 (12): 568-581, 1964

10 Nazif, H, "Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows" 7 (7): 95-101, 2010

11 Gendreau, M., "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem" 40 (40): 1086-1094, 1992

12 Blanton J. L, "Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms, Proceeding of the 5th International Conference Genetic Algorithms" Morgan Kaufmann Publishing 452-459, 1993

13 Gambardella, L. M., "MACS-VRPTW：A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows" Technical Report IDSIA-06-99 1999

14 Reimann, M., "D-ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem" 31 (31): 563-591, 2004

15 Magnanti, T. L, "Combinatorial Optimization and Vehicle Fleet Planning: Perspectives and Prospects" 11 (11): 179-213, 1981

16 Bullnheimer, B., "Applying the Ant System to the Vehicle Routing Problem" 1997

17 Goldberg, D, "Alleles, Loci, and The Traveling Salesman Problem" 154-159, 1985

18 Solomon M. M., "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints" 35 (35): 254-265, 1987

19 Holland, J. H., "Adaption in Natural and Artificial Systems" University of Michigan Press 1975

20 Garcia, B. L., "A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints" 21 : 1025-1033, 1994

21 Cook, W, "A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows, Technical Report" Computational and Applied Mathematics, Rice University, 1999