시간제약과 하역장 용량제약이 있는 차량경로문제에 대한 타부탐색 알고리즘 = A Tabu Search Algorithm for the Vehicle Routing Problem with Time Window and Dock Capacity Constraints

다국어 초록 (Multilingual Abstract)

We consider a vehicle routing problem with time window and dock capacity constraints (VRPTD). In most traditional models of vehicle routing problems with time window (VRPTW), each customer must be assigned to only one vehicle route. However demand of a customer may exceed the capacity of one vehicle, hence at least two vehicles may need to visit the customer. We assume that each customer has its own dock capacity. Hence, the customer can be served by only a limited number of vehicles simultaneously. Given a depot, customers, their demands, their time windows and dock capacities, VRPTD is to get a set of feasible routes which pass the depot and some customers such that all demands of each customer are satisfied. Since VRPTD is NP-hard, a meta-heuristic algorithm is developed. The algorithm consists of two procedures; the route construction procedure and the route scheduling procedure. We tested the algorithm on a number of instances and computational results are reported.

참고문헌 (Reference)

1 "지연 비용을 고려한 서비스 시간대가 존재하는 외판원 문제에 대한 발견적 해법" 27 (27): 18-24, 2001

2 "The Shifting Bottleneck Procedure for Job-Shop Scheduling" 34 (34): 391-401, 1988

3 "Surrogate Duality Relaxation for Job-Shop Scheduling" 5 (5): 65-75, 1983

4 "Scheduling the General Job-Shop" 31 (31): 594-598, 1985

5 "Scheduling of Vehicles from A Central Depot to A Number of Delivery Points" no.4 : 568-581, 1964

6 "Scheduling Aircraft Landings The Static Case" 34 (34): 2000

7 "Heuristic Methods for Vehicle Routing Problem with Time Windows" 15 (15): 281-295, 2001

8 "Future Paths for Integer Programming and Links to Artificial Intelligence" no.5 : 533-549, 1986

9 "Classification in Vehicle Routing and Scheduling" 11 : 97-108, 1981

10 "An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints" 26 (26): 69-85, 1992

11 "An Exchange Heuristic Imbedded with Simulated Annealing for Due-Dates Job-Shop Scheduling" no.1 : 99-117, 1994

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

13 "A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem" 100 (100): 180-191, 1997

14 "A Heuristic for Scheduling General Job Shops to Minimize Maximum Lateness" 27 (27): 1-15, 1998

15 "A Comparison of Dispatching Rules for Job with Multiple Identical Jobs and Alternative Routings" 28 : 953-962, 1990