Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking

Authors

Huimin Niu
Xuesong Zhou
Xiaopeng Tian

Document Type

Journal Article

Publication Date

2018

Subject Area

planning - route design, planning - methods, infrastructure - fleet management, operations - scheduling, operations - reliability, technology - intelligent transport systems

Keywords

Transit vehicle scheduling, Coordination, Lagrangian relaxation, Network reduction, Symmetry breaking

Abstract

This paper focuses on how to coordinate a critical set of assignment and routing decisions in a class of multiple-depot transit vehicle scheduling problems. The assignment decision aims to assign a set of transit vehicles from their current locations to trip tasks in a given timetable, where the routing decision needs to route different vehicles to perform the assigned tasks and return to the depot or designated layover locations. When applying the general purpose solvers and task-oriented Lagrangian relaxation framework for real world instances, a thorny issue is that different but indistinguishable vehicles from the same depot or similar locations could commit to the same set of tasks. This inherent solution symmetry property causes extremely difficult computational barriers for effectively eliminating identical solutions, and the lower bound solutions could contain many infeasible vehicle-to-task matches, leading to large optimality gaps. To systematically coordinate the assignment and routing decisions and further dynamically break symmetry during the solution search process, we adopt a variable-splitting approach to introduce task-specific and vehicle-distinguishable Lagrangian multipliers and then propose a sequential assignment process in order to enhance the solution quality for the augmented models with tight formulations. We conduct the numerical experiments to offer the managerial interpretation and examine solution quality of the proposed approach in a wider range of applications.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part B Home Page:

http://www.sciencedirect.com/science/journal/01912615

Recommended Citation

Niu, H., Zhou, X., & Tian, X. (2018). Coordinating assignment and routing decisions in transit vehicle schedules: A variable-splitting Lagrangian decomposition approach for solution symmetry breaking. Transportation Research Part B: Methodological, Vol. 107, pp. 70-101.