Shortest Path Problems with Resource Constraints

• Applicants: Professor Dr. Timo Gschwind; Professor Dr. Stefan Irnich
• Subject Area: Accounting and Finance
• Term: since 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 418727865

Vehicle routing and crew scheduling are among the most important problems in Operations Research. Vehicle routing problems ask for a set of minimum-cost vehicle routes performed by a given fleet of vehicles that fulfill a set of transportation requests (e.g. customer visits) subject to side constraints. Crew scheduling problems consist of finding optimal feasible work plans (schedules must satisfy work rules), one for each crew member (pilots, cabin crews, drivers of trains, buses or ships), that cover a given set of activities. Numerous variants of both problem types exist. The use of optimization methods offers substantial cost savings due to the automation of the planning process and the higher quality of the planning results.The leading exact solution approaches for vehicle routing and crew scheduling are based on Branch-Cut-and-Price (BCP) which employs column-generation techniques. A master program selects the best among a working set of routes or schedules, while one or several pricing problems (=subproblems) dynamically generate missing routes and schedules. This subproblem is known as the Shortest Path Problem with Resource Constraints (SPPRC). Simple resource constraints result from the vehicle capacity, time windows, and a maximum shift duration. In many practically relevant applications, several additional attributes are necessary to model more complex interdependencies between resources. Standard approaches for the solution of SPPRCs are based on dynamic programming labeling algorithms.Recent computational studies show that in many BCP algorithms for vehicle routing and crew scheduling the solution of the SPPRC pricing problem consumes more than 95% of the computation time. Any acceleration of SPPRC algorithms therefore directly transfers to an improved performance of the overall solution approach. The general goal of the project is to develop and analyze new methods for the solution of SPPRCs, generating new theoretical and practical insights into SPPRCs. The focus is on the development of new generic components of effective labeling algorithms as well as on solving new problem variants. This includes the implementation of the proposed techniques for specific applications and their evaluation in computational studies.

• DFG Programme: Research Grants