Vehicle Routing Problem with Simultaneous Delivery and Pick-Up with Time Windows
Publication: International Conference on Transportation Engineering 2007
Abstract
The vehicle routing problem with simultaneous delivery and pick-up with time windows (VRP-SDPTW) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous delivery and pick-up service within the time windows. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of delivery and pick-up loads, at the same time in any route the vehicle can not violate some constraints, such as: the vehicle capacity time windows and traveling distance constraints. VRP-SDPTW as an extension for vehicle routing problem, which is a complex combinational optimization problem, and is a well know non-polynomial hard (NP-hard) Problem. In this paper, VRP-SDPTW is presented from the point of strategic view that combines the logistics and reverse logistics (bidirectional logistics). We constructed a universal mix integer programming mathematic model of VRP-SDPTW in detail, which can transform into other typical combination optimal problems by setting different parameters. An improved genetic algorithm (IGA) is proposed based on the novel crossover-operator to solve the problem. In operation process, we firstly adopted the novel decimal coding according to a priori sequence among all customers, which consider effectively the vehicle capacity time windows and traveling distance restrictions at the same time. And then a novel crossover-operator is designed. The improved genetic algorithm (IGA) avoids effectively the common defects of early convergence and the diversity of population in traditional genetic algorithm. The experiment result shows that this algorithm can find the optimal or near-optimum solution to VRP-SDPTW effectively.
Get full access to this article
View all available purchase options and get full access to this chapter.
Information & Authors
Information
Published In
Copyright
© 2007 American Society of Civil Engineers.
History
Published online: Apr 26, 2012
ASCE Technical Topics:
- Algorithms
- Continuum mechanics
- Design (by type)
- Dynamic loads
- Dynamics (solid mechanics)
- Engineering fundamentals
- Engineering mechanics
- Foundation design
- Foundations
- Freight transportation
- Geotechnical engineering
- Highway transportation
- Infrastructure
- Load bearing capacity
- Load factors
- Logistics
- Mathematics
- Routing (transportation)
- Solid mechanics
- Structural design
- Structural dynamics
- Structural engineering
- Structural systems
- Traffic engineering
- Transportation engineering
- Vehicle loads
- Vehicles
- Windows
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.