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

Huimin Niu, Xuesong Zhou and Xiaopeng Tian

Transportation Research Part B: Methodological, 2018, vol. 107, issue C, 70-101

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.

Keywords: Transit vehicle scheduling; Coordination; Lagrangian relaxation; Network reduction; Symmetry breaking (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516306208
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:107:y:2018:i:c:p:70-101

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2017.11.003

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().