Genetic Algorithm Based Heuristic Method for Time Window and Capacity Constrained Pickup and Delivery Vehicle Routing Problem
Date Issued
2008
Date
2008
Author(s)
Lai, Ching-Shan
Abstract
Due to the increasing demand of point-to-point parcel deliveries in metropolitan area, a time window and capacity constrained one-to-one pickup and delivery single vehicle routing problem arises. This paper rigorously defined this problem and then proposed GA-based heuristic methods for the problem. In this problem, pickup and delivery points are exclusively defined and paired with a one-on-one and pickup-delivery relationship. The time window constraint for the pickup/delivery service times imposed on each point is regarded as soft constraints in this problem. Therefore, the goal of the problem is to find a route with a minimal routing distance and a minimal amount of time window violation. To assure a route satisfying the capacity and one-on-one pickup and delivery constraints, this paper presents a heuristic operation named as “guided merge operation (GMO).” GMO can be used to generate hard constraints satisfied routes to serve as the initial population for a GA-based solving model. It can be used to repair constraint-violated routes generated from traditional GA crossover and mutation operations. In addition, GMO is further enhanced to serve as a GA crossover operator that can generate two constraint-satisfied child routes from two parent ones. Without changing the optimal route, several benchmarks from the TSPLIB were adapted and transformed into sample problems for the problem by adding pickup/delivery one-on-one attribute and the earliest and latest service times to each city. Three GA computation models were constructed for the numerical tests: a simple GA, a GA+GMO-based repairing, and a GA with the GMO-crossover operator. Results indicated that the model with GMO repairing model outperformed others. However, the GMO-crossover operation requires further improvement.
Subjects
Time Window Constraints
TSP
Guided Merge Operation
Genetic Algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95546018-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):29535feeb8258d53fb681bba99326706