Computational Methods for Large-Scale Vehicle Routing Problems
February 17, 2023
12 PM – 1 PM ET
This talk covers recent developments in computational methods for three large-scale routing problems: the capacitated vehicle routing problem (CVRP), the traveling salesman problem with drones (TSP-D), and the multi-depot vehicle routing problem (MD-VRP). In the first part, we will present a method for generating cutting planes using neural networks within the branch-and-cut algorithm for CVRP and demonstrate that it outperforms the current standard algorithm package, CVRPSEP. In the second part, we will describe a hybrid heuristic algorithm that combines genetic search, dynamic programming, and local searches to solve TSP-D, with a novel type-aware chromosome encoding that finds 1,143 new best solutions among 1,682 benchmark instances. In the third part, we will demonstrate how a simple genetic algorithm with a learning-based individual evaluator can be devised to solve the hierarchical routing problem of MD-VRP, utilizing existing high-performance solvers for CVRP.
Changhyun Kwon is an associate professor of industrial and management systems engineering at the University of South Florida. His research area is computational optimization methods for transportation systems and logistics, which has been supported by various organizations, including the National Science Foundation, the U.S. Department of Transportation, Toyota Material Handling North America, and the Canadian Embassy. He received his Ph.D. in industrial engineering in 2008, his M.S. in industrial engineering and Operations Research in 2005, and a B.S. in mechanical engineering from KAIST in 2000. He was awarded the NSF CAREER award in 2014 and the UB Exceptional Scholar: Young Investigator Award in 2015. He is an active member of INFORMS and TRB, where he has held various leadership roles.