Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows

Duman, Ece Naz and Taş, Duygu and Çatay, Bülent (2021) Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows. International Journal of Production Research . ISSN 0020-7543 (Print) 1366–588X (Online) Published Online First http://dx.doi.org/10.1080/00207543.2021.1955995

Warning
There is a more recent version of this item available.
Full text not available from this repository. (Request a copy)

Abstract

In this paper, we address the electric vehicle routing problem with time windows and propose two branch-and-price-and-cut methods based on a column generation algorithm. One is an exact algorithm whereas the other is a heuristic method. The pricing sub-problem of the column generation method is solved using a label correcting algorithm. The algorithms are strengthened with the state-of-the-art acceleration techniques and a set of valid inequalities. The acceleration techniques include: (i) an intermediate column pool to prevent solving the pricing sub-problem at each iteration, (ii) a label correcting method employing the ng-route algorithm adopted to our problem, (iii) a bidirectional search mechanism in which both forward and backward labels are created, (iv) a procedure for dynamically eliminating arcs that connect customers to remote stations from the network during the path generation, (v) a bounding procedure providing early elimination of sub-optimal routes, and (vi) an integer programming model that generates upper bounds. Numerical experiments are conducted using a benchmark data set to compare the performances of the algorithms. The results favour the heuristic algorithm in terms of both the computational time and the number of instances solved. Moreover, the heuristic algorithm is shown to be specifically effective for larger instances. Both algorithms introduce a number of new solutions to the literature.
Item Type: Article
Uncontrolled Keywords: branch-and-price-and-cut; column generation; electric vehicles; labelling algorithms; Routing
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Bülent Çatay
Date Deposited: 10 Feb 2022 18:16
Last Modified: 30 Aug 2022 12:57
URI: https://research.sabanciuniv.edu/id/eprint/42667

Available Versions of this Item

Actions (login required)

View Item
View Item