A bidirectional branch-and-price algorithm with pulse procedure for the electric vehicle routing problem with flexible deliveries

Warning The system is temporarily closed to updates for reporting purpose.

Duman, Ece Naz and Taş Küten, Duygu and Çatay, Bülent (2024) A bidirectional branch-and-price algorithm with pulse procedure for the electric vehicle routing problem with flexible deliveries. Transportation Research Part C: Emerging Technologies, 165 . ISSN 0968-090X (Print) 1879-2359 (Online)

Full text not available from this repository. (Request a copy)

Abstract

Delivery flexibility offers customers the convenience of receiving their orders at a location and time that best suits their schedule. Moreover, it enables delivery companies to better manage their operations and decrease costs. Nonetheless, this flexibility brings added complexities to route optimization. This study focuses on the Electric Vehicle Routing Problem with Flexible Deliveries, which becomes more challenging when the fleet comprises electric vehicles with limited autonomy. To solve this problem, we develop a novel column generation method embedded within a bidirectional branch-and-price algorithm enhanced with Pulse procedure. We adopt an enhanced bidirectional algorithm to solve the pricing subproblem to overcome common weaknesses of the classical labeling algorithms such as label storing. The BP is improved with state-of-the-art acceleration techniques including (i) a bidirectional search mechanism in which both forward and backward labels are created, (ii) a method to prevent solving the pricing sub-problem at each iteration, and (iii) an integer programming model that generates upper bounds. We present a new data set including instances with up to 120 customers and an extensive computational study evaluating the performance of the proposed BP algorithm. Our results show that the proposed algorithm can effectively solve instances with up to 60 customers, 237 delivery locations, and 13 recharging stations.
Item Type: Article
Uncontrolled Keywords: Branch-and-price; Column generation; Electric vehicles; Flexible deliveries
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Duygu Taş Küten
Date Deposited: 29 Jul 2024 11:37
Last Modified: 29 Jul 2024 11:37
URI: https://research.sabanciuniv.edu/id/eprint/49553

Actions (login required)

View Item
View Item