Heuristic Algorithms for Capacity constrained Pickup and Delivery Vehicle Routing Problems
Date Issued
2006
Date
2006
Author(s)
Huang, Hsin-Yi
DOI
zh-TW
Abstract
Due to the increasing of point-to-point parcel deliveries in metropolitan area, capacity constrained pickup and delivery vehicle routing problems become popular. This paper presents several algorithms and methods for constructing and improving solutions. Compared with traditional Vehicle Routing Problem, this problem has introduced a one-follow-one precedence constraint on the routing sequence and a vehicle capacity constraint along the routing. Customers are partitioned into a pickup and delivery ones and paired with a pickup and a delivery customer. A vehicle having a limited parcel capacity starts from a depot and visits each customer exactly once with each pickup customer visited before the delivery target customer. The objective is to minimize the route length. This research proposes five route constructing algorithms and four improving methods. In addition, two computation modes are presented to solve this problem using these algorithms and methods: 1) two-stage mode, constructing a route then improving it, and 2) single-stage mode, constructing and improving the route step by step. Benchmarks of TSP-LIB are adopted and converted into capacity constrained pickup and delivery vehicle routing problems without changing the optimum routing solutions. The proposed constructing algorithms and improving methods are crossly combined to establish various computation cases to solve the numerical problems. Results are compared for those proposed algorithms and methods and conclusions are addressed.
Subjects
旅行推銷員問題
一對一取卸貨途程問題
Vehicle Routing Problem
VRP
TSP
Pickup and delivery Vehicle Routing Problem
PDVRP
Type
thesis