Abstract
We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.
| Original language | English |
|---|---|
| Pages (from-to) | 32-52 |
| Number of pages | 21 |
| Journal | Transportation Research. Part E: Logistics and Transportation Review |
| Volume | 86 |
| DOIs | |
| Publication status | Published - 1 Feb 2016 |
| Externally published | Yes |
Funding
The authors thank Editor Prof. Jiuh-Biing Sheu and four anonymous referees for their constructive suggestions, which helped improve the content and presentation of this article. They also thank Prof. W.E.H. Dullaert for his valuable comments and feedback. The work of the third author is partially supported by GRF grant CUHK414313 from the Hong Kong Research Grants Council.
Keywords
- Fixed sequence arc selection
- Heterogeneous fleet
- HVRP
- Multigraph
- Tabu search
- Vehicle routing