A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows

Yang Yu, Sihan Wang, Junwei Wang and Min Huang

Transportation Research Part B: Methodological, 2019, vol. 122, issue C, 511-527

Abstract: Heterogeneous fleet vehicles can be used to reduce carbon emissions. We propose an improved branch-and-price (BAP) algorithm to precisely solve the heterogeneous fleet green vehicle routing problem with time windows (HFGVRPTW). In the improved BAP, to speed up the solution for the pricing problem, we develop a multi-vehicle approximate dynamic programming (MVADP) algorithm that is based on the labeling algorithm. The MVADP algorithm reduces labels by integrating the calculation of pricing problems for all vehicle types. In addition, to rapidly obtain a tighter upper bound, we propose an integer branch method. For each branch, we solve the master problem with the integer constraint by the CPLEX solver using the columns produced by column generation. We retain the smaller of the obtained integer solution and the current upper bound, and the branches are thus reduced significantly. Extensive computational experiments were performed on the Solomon benchmark instances. The results show that the branches and computational time were reduced significantly by the improved BAP algorithm.

Keywords: Heterogeneous fleet; Green vehicle routing problem; Branch-and-price (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261518308944
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:transb:v:122:y:2019:i:c:p:511-527

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2019.03.009

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().