Vehicle Routing with Heterogeneous Time Windows

Petra Mutzel, Tim Niemann (), Lukas Schürmann, Sebastian Stiller and Andreas M. Tillmann
Additional contact information
Petra Mutzel: Universität Bonn
Tim Niemann: Technische Universität Braunschweig
Lukas Schürmann: Universität Bonn
Sebastian Stiller: Technische Universität Braunschweig
Andreas M. Tillmann: Technische Universität Braunschweig

Chapter Chapter 21 in Operations Research Proceedings 2022, 2023, pp 171-177 from Springer

Abstract: Abstract We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous VRPs typically distinguishes properties of the vehicle fleet such as costs or capacities, but apparently, windows of customers have only been regarded in a homogeneous fashion thus far. To solve the problem, we employ a branch-and-price framework based on a set partitioning formulation together with a parallelizable labeling algorithm. The heterogeneous time window structure yields notable computational gains by allowing to decompose the pricing problem as well as to utilize a customer-vehicle assignment branching rule. We show that this branching rule leads to more balanced search trees than the usual arc flow branching, and demonstrate its efficiency in numerical experiments.

Keywords: Vehicle routing problem; Heterogeneous time windows; Branch and price (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:lnopch:978-3-031-24907-5_21

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_21

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().