Electric Vehicle Routing Problem with Time Windows
and Waiting Times at Recharging Stations
January 26th at 14:30
Virtual room on Teams platform
In the Electric Vehicle Routing Problem with Time Windows (EVRPTW), the vehicles have a limited driving range and may need to recharge their battery en-route at shared recharging stations. Most of the studies on the EVRPTW assume that recharging at a station starts as soon as the vehicle arrives. However, in practice, the number of chargers in a station is limited and the vehicles may wait in a queue before the recharging service starts. Since the customers and the depot are associated with time windows, waiting times at the stations in addition to the recharging times may cause disruptions in logistics operations. In this talk, we extend the EVRPTW by using an M/M/1 queueing system at the stations and discuss two problem variants. In the first problem, we consider time-dependent waiting times assuming that the expected queue lengths at all stations and at any time of the day are known in advance. Furthermore, the charging time is a non-linear concave function of the charge amount. We allow but penalize late arrivals at customer locations and at the depot. We minimize the total cost of vehicles, drivers, energy, and penalties for late arrivals. We formulate the problem as a mixed integer linear program and propose a matheuristic approach using the Adaptive Large Neighborhood Search (ALNS), which benefits from several problem-specific operators. In the second problem, we omit the time-dependency and non-linear charging function because of the complexity but consider random queueing times at the stations. We assume that the probability distributions of the waiting times are known, but the exact times are revealed when the vehicle arrives at the station. We formulate this problem as a two-stage model. In the first stage, a set of routes is determined. In the second stage, random queueing times are realized when each route is executed and a recourse action is taken to correct the first-stage solution. To solve this problem, we present a simulation-based heuristic using ALNS enhanced by a new adaptive mechanism that tunes the constant waiting times used in finding the first-stage solution. Our experiments validated the performance of the proposed methods in terms of solution quality and computational time. It also revealed that waiting times might have significant impact on route plans.
Short bio: Bülent Çatay is a Professor of Industrial Engineering at Sabanci University, Istanbul. He received his B.Sc. degree in Industrial Engineering from Istanbul Technical University and his Ph.D. degree in Operations Management from the University of Florida. He worked as a consultant at IBM Microelectronics in Burlington, Vermont in 1997 and as a visiting lecturer at the University of Florida during 1999-2000. His research interests include sustainable transport planning, vehicle routing, electrification of logistics operations, and applied optimization. He has published over 80 articles and chapters in various international and national scientific journals, conference proceedings, and edited books. He is the recipient of IBM Faculty Award and founding director of the Smart Mobility and Logistics Laboratory at Sabanci University.
For more information:
Ornella Pisacane email@example.com
Joint work with Merve Keskin and Gilbert Laporte