The multi-trip vehicle routing problem with time windows and unloading queue at depot

Nan Huang, Jiliu Li, Wenbin Zhu and Hu Qin

Transportation Research Part E: Logistics and Transportation Review, 2021, vol. 152, issue C

Abstract: Motivated by the practice of urban waste collection, we introduce a new variant of the multi-trip vehicle routing problem with time windows, where vehicles unload cargos collected from customers at a depot that owns a limited unloading capacity, and therefore some vehicles need to wait at a queue once the unloading capacity is fully occupied. Unloading queue at depot significantly compicates this problem since it makes a trip involve traveling, waiting, and unloading stages. We first formulate this problem into a trip-based set partitioning model, which has two sets of mutual exclusion constraints. To solve the model, we propose a branch-and-price-and-cut algorithm (BPC), in which the linear relaxation of the model is solved by column generation, and moreover, the relaxation gap is tightened by incorporating rounded capacity inequalities. Particularly, the mutual exclusion constraints induce a new and challening pricing problem, and we design a novel label-setting algorithm with tailored label structure to solve it. We conduct compuational experiments on a set of random instances generated from the Solomon’s benchmark, and the results demonstrate the effectiveness of the proposed model and algorithm.

Keywords: Multi-trip; Vehicle routing; Unloading queue; Branch-and-price-and-cut (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554521001381
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:152:y:2021:i:c:s1366554521001381

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2021.102370

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().