Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems

Arne Schulz and Christian Pfeiffer

European Journal of Operational Research, 2024, vol. 312, issue 2, 456-472

Abstract: The paper introduces a fixed-path procedure to solve precedence-constrained routing problems. The procedure can be applied within a branch-and-cut framework to improve the search with respect to arrival time variables. Every time when a new variable is fixed in a branch-and-cut node, the fixed-path procedure tries to improve lower bounds on variables picturing the arrival time at customer locations. With the help of these lower bounds, we can identify infeasible solutions ahead of time, fix additional arc variables, and add additional valid inequalities. The fixed-path procedure is evaluated for several objective functions for the dial-a-ride problem. Moreover, we apply it to a dial-a-ride problem focusing on the residents of large cities. These individuals have access to a wide range of means of transportation. Therefore, ridepooling providers have to solve the trade-off between the costs for deployed vehicles and small detours for customers to be competitive. We evaluate our fixed-path procedure in an extensive computational study with 4500 instances with up to 120 customers and 10 vehicles for this problem. With the fixed-path procedure, we were able to solve 838 (29.9%) additional problem instances to optimality and to find better lower and upper bounds than a standard mixed-integer programming formulation.

Keywords: Routing; Dial-a-ride problem; Branch-and-cut; Fixed paths; Valid inequalities (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723005398
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:ejores:v:312:y:2024:i:2:p:456-472

DOI: 10.1016/j.ejor.2023.07.002

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().