A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management

• Published in: Operations research 2019-11, Vol.67 (6), p.1586-1609
• Main Authors: Lamorgese, Leonardo, Mannino, Carlo
• Format: Article
• Language: English
• Subjects: algorithms; Benders' decomposition; Bending machines; Integer programming; Job shop scheduling; Job shops; Linear programming; Operations research; Rescheduling; Schedules; Scheduling; Scheduling algorithms; Traffic congestion; Traffic control; Traffic management; Transportation; Transportation technology; transportation: scheduling, vehicles
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2018.1837

Vehicle scheduling is a central problem in transportation. As railways and the airspace become increasingly congested, it is crucial to develop mathematical tools to better schedule trains and airplanes off-line (timetabling) and online (dispatching). These traffic-management problems can be modeled as job-shop scheduling problems, which, in turn, can be solved using mixed-integer linear programming (MILP). The two most successful and widespread formulations in the past decades are the big- M and the time-indexed methods, each with its strengths and weaknesses. However, there have been few advancements in either approach in recent years. In this paper, we introduce an alternative formulation, obtained by strengthening and lifting the Benders' reformulation of a natural initial formulation. This new approach improves performances on our real-life test bed and opens up interesting research directions. A central problem in traffic management is that of scheduling the movements of vehicles so as to minimize the cost of the schedule. It arises in important applications such as train timetabling, rescheduling, delay and disruption management, airplane surface routing, runway scheduling, air-traffic control, and more. This problem can be modeled as a job-shop scheduling problem. We introduce a new mixed-integer linear program (MILP) formulation for job-shop scheduling, which is an alternative to classical approaches, namely, big- M and time-indexed formulations. It does not make use of artificially large coefficients, and its constraints correspond to basic graph structures, such as paths, cycles, and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. Tests on a large set of real-life instances from train rescheduling show that the new approach performs on average better than our previous approaches based on big- M formulations and particularly better on a class of instances with nonconvex costs very common in the practice.