Master Thesis: Optimizing the Electric Vehicle Routing Problem with the Adaptive Large Neighborhood

Job description

Master thesis: Optimizing the Electric Vehicle Routing Problem with the Adaptive Large Neighborhood Search Algorithm

Background
Throughout the past decades, optimization techniques have seen widespread use within the field of logistics to increase efficiency and productivity. One of the problems that has been subject to optimization is the NP-hard Vehicle Routing Problem (VRP), a generalization of the well-known Traveling Salesperson Problem (TSP). In the VRP, one tries to find a way to route a fleet of vehicles so that they jointly perform a predefined set of deliveries in the most efficient way possible, which can be thought of as the TSP with multiple traveling salespeople. While the basic VRP has been studied in detail, one of its variants, the Electric Vehicle Routing Problem (EVRP), is less well-studied. This variant is, however, of increasing importance as the transportation industry moves away from fossil fuels, and electric trucks are becoming more commonplace.

 

While the EVRP bears great resemblance to the standard VRP, there are some unique aspects that set it apart from the standard variant. The most complicating—and therefore important—aspect is the fact that electric trucks typically need to recharge their batteries one or more times during the working day, which can add hours to delivery times if not well planned. As such, new methods and insights are key for optimizing vehicle routing for electric trucks, and an important step for widespread electrification of the world’s truck fleet. An overview of the EVRP, its variations, and solution methods can be found in [1].

 

Project description
In this project, you will apply a heuristic solution method known as Adaptive Large Neighborhood Search (ALNS) to the EVRP. ALNS was first introduced by Røpke and Pisinger in 2006 [2], and is a heuristic method that takes an initial solution and iteratively ruins the solution before recreating it in a slightly different shape. It does this by randomly selecting one of several destroy operators, and one of several repair operators, where the probability of selecting a specific operator depends on how successful it has been so far. A survey on the algorithm and its applications can be found in [3].

 

ALNS has been used for various versions of the VRP—including the EVRP—with great success, both as the sole solution method [4], and in combination with classical, exact Mixed-Integer Programming (MIP) approaches [5]. The combination of ALNS and exact solution methods is of particular interest, since ALNS typically finds good solutions quickly, but isn't guaranteed to ever find an optimum, nor does it provide so-called optimality gaps for its solutions, which would indicate how close said solutions are to optimality. Exact methods, however, find an optimum eventually, and calculate optimality gaps for their intermediate solutions during the optimization process. As such, integrating the two in a smart way has the potential to let one find an optimal or near-optimal solution quickly, or at least to obtain good solutions and their corresponding optimality gaps.

 

In this thesis, you will choose which aspects of ALNS for EVRP to focus on, and make your own contribution to the scientific knowledge surrounding ALNS and its applicability for the EVRP, bringing us one step closer to a decarbonized transportation industry.

 

Research questions
Potential research questions include:

Which aspects of the EVRP can be handled appropriately by ALNS? Aspects may include:
Delivery time windows
Handling a fleet of mixed truck configurations, varying in battery size, capacity, etc
The mass of the truck changing as items are loaded/unloaded throughout the trip
The nonlinear relationship between the charging power from a charging station and the truck’s battery level
Which destroy and recreate operators are appropriate for the EVRP? Does this change as the solution improves? Are any operators useful in general for the EVRP, or does a successful implementation of ALNS require operators to to be tailored to the problem-specific aspects like the ones listed above?
Can ALNS be used in conjunction with exact methods, such as column generation/branch-and-price for the EVRP? Does this lead to better solution quality? Should the two methods be intertwined with each other, or is it better to generate and initial solution with ALNS and then improve it with exact methods?
Can ALNS for EVRP be parallelized to achieve speedups? For what instance sizes—if any—are these speedups significant?
 

The list above is not exhaustive, and any ideas you have yourself are most welcome.

 

Deliverables
The concrete aim of this thesis is to develop an implementation of ALNS for EVRP and to evaluate its performance in terms of runtime and solution quality, as well as other relevant aspects—such as optimality gaps—if applicable. The evaluation should be done through a comparison to a relevant baseline—like a basic MIP model solved by a commercial MIP solver—on appropriate benchmark instances from the literature.

 

Student background
The thesis is intended for one or two master's students. Appropriate educational backgrounds include master's programs related to Engineering Mathematics, Engineering Physics, Computer Science, and others with an emphasis on mathematics and programming. Experience with the following is beneficial:

Linear and integer optimization
Algorithm design
High-performance programming languages, such as C, C++, or Rust
Stochastic methods for optimization
Large-scale optimization
 

When applying, please provide your CV, a cover letter, and your transcript of grades, by the 7th of Novemberat the latest.

 

Contact
Don’t hesitate to reach out with any questions about the thesis.

 

Joseph Löfving, joseph.lofving@volvo.com.

 

References
[1] Ilker Kucukoglu, Reginald Dewil, and Dirk Cattrysse. “The electric vehicle routing problem and its variations: A literature review”. In: Computers & Industrial Engineering 161 (Nov. 2021). issn: 03608352. doi: 10.1016/j.cie.2021.107650. url: https://linkinghub.elsevier.com/retrieve/pii/S0360835221005544.

 

[2] Stefan Ropke and David Pisinger. “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows”. In: Transportation Science 40.4 (Nov. 2006), pp. 455–472. issn: 0041-1655, 1526-5447. doi: 10.1287/trsc.1050.0135. url: https://pubsonline.informs.org/doi/10.1287/trsc.1050.0135.

 

[3] Setyo Tri Windras Mara et al. “A survey of adaptive large neighborhood search algorithms and applications”. In: Computers & Operations Research 146 (Oct. 2022), p. 105903. issn: 03050548. doi: 10.1016/j.cor.2022.105903. url: https://linkinghub.elsevier.com/retrieve/pii/S0305054822001654.

 

[4] Glaydston Mattos Ribeiro and Gilbert Laporte. “An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem”. In: Computers & Operations Research 39.3 (Mar. 2012), pp. 728–735. issn: 03050548. doi: 10.1016/j.cor.2011.05.005. url: https://linkinghub.elsevier.com/retrieve/pii/S0305054811001298.

 

[5] V. Pillac, C. Guéret, and A. L. Medaglia. “A parallel matheuristic for the technician routing and scheduling problem”. In: Optimization Letters 7.7 (Oct. 2013), pp. 1525–1535. issn: 1862-4472, 1862-4480. doi: 10 . 1007 / s11590 - 012 - 0567 - 4. url: http://link.springer.com/10.1007/s11590-012-0567-4.

...

Job Category:  Technology Engineering

Organization:  Group Trucks Technology

Travel Required:  No Travel Required

Requisition ID:  14948