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

Schulz, Arne; Pfeiffer, Christian

doi:10.1016/j.ejor.2023.07.002

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

Publication date

2023-07-06

Document type

Forschungsartikel

Author

Schulz, Arne

Pfeiffer, Christian

Organisational unit

Universität Hamburg, Institute of Operations Management

DOI

10.1016/j.ejor.2023.07.002

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22183

Scopus ID

2-s2.0-85165142000

Publisher

Elsevier

Series or journal

European Journal of Operational Research

ISSN

0377-2217

Periodical volume

312

Periodical issue

2

First page

456

Last page

472

Part of the university bibliography

Nein

Language

English

Keyword

Branch-and-cut

Dial-a-ride problem

Fixed paths

Routing

Valid inequalities

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.

Description

This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)

Version

Published version

Access right on openHSU

Metadata only access