A branch-and-cut algorithm for a skip pick-up and delivery problem

José M. Belenguer; Maximiliano Cubillos; Sanne Wøhlk

doi:10.1016/j.cor.2024.106705

A branch-and-cut algorithm for a skip pick-up and delivery problem

José M. Belenguer, Maximiliano Cubillos, Sanne Wøhlk^*

^*Corresponding author for this work

Department of Economics and Business Economics

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

1 Citation (Scopus)

Abstract

In this study we present a branch-and-cut algorithm for a skip pick-up and delivery problem. The study is motivated by a real-life problem in which full skips are transported from waste drop-off stations to treatment facilities where they are emptied, and then brought back to the original drop-off station. The transportation of the skips is done by trucks with the capacity of carrying two containers at a time. The planning problem is to design the routes of the trucks that perform the collection to satisfy a number of requests in a planning period. A truck route starts at the first pick-up, the truck then performs a sequence of pick-ups, treatments, and deliveries, and the route ends at the last delivery. From the truck perspective, the three actions of pick-up, treatment, and delivery can be performed in any order that respects the vehicle capacity of two and the route duration constraint, but for the single request, the three actions must be performed in the stated order. The problem is formulated as a mixed integer linear problem and several classes of valid inequalities are proposed and integrated into a branch-and-cut algorithm.

Original language	English
Article number	106705
Journal	Computers and Operations Research
Volume	168
ISSN	0305-0548
DOIs	https://doi.org/10.1016/j.cor.2024.106705
Publication status	Published - Aug 2024

Keywords

Branch-and-cut
Pick-up and delivery problems
Skip transport
Transport
Waste

Access to Document

10.1016/j.cor.2024.106705Licence: CC BY

OpenUrl availability

Full text

Cite this

@article{4cda4e7859e34e948befb718fa04f2e8,

title = "A branch-and-cut algorithm for a skip pick-up and delivery problem",

abstract = "In this study we present a branch-and-cut algorithm for a skip pick-up and delivery problem. The study is motivated by a real-life problem in which full skips are transported from waste drop-off stations to treatment facilities where they are emptied, and then brought back to the original drop-off station. The transportation of the skips is done by trucks with the capacity of carrying two containers at a time. The planning problem is to design the routes of the trucks that perform the collection to satisfy a number of requests in a planning period. A truck route starts at the first pick-up, the truck then performs a sequence of pick-ups, treatments, and deliveries, and the route ends at the last delivery. From the truck perspective, the three actions of pick-up, treatment, and delivery can be performed in any order that respects the vehicle capacity of two and the route duration constraint, but for the single request, the three actions must be performed in the stated order. The problem is formulated as a mixed integer linear problem and several classes of valid inequalities are proposed and integrated into a branch-and-cut algorithm.",

keywords = "Branch-and-cut, Pick-up and delivery problems, Skip transport, Transport, Waste",

author = "Belenguer, {Jos{\'e} M.} and Maximiliano Cubillos and Sanne W{\o}hlk",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2024",

month = aug,

doi = "10.1016/j.cor.2024.106705",

language = "English",

volume = "168",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - A branch-and-cut algorithm for a skip pick-up and delivery problem

AU - Belenguer, José M.

AU - Cubillos, Maximiliano

AU - Wøhlk, Sanne

PY - 2024/8

Y1 - 2024/8

N2 - In this study we present a branch-and-cut algorithm for a skip pick-up and delivery problem. The study is motivated by a real-life problem in which full skips are transported from waste drop-off stations to treatment facilities where they are emptied, and then brought back to the original drop-off station. The transportation of the skips is done by trucks with the capacity of carrying two containers at a time. The planning problem is to design the routes of the trucks that perform the collection to satisfy a number of requests in a planning period. A truck route starts at the first pick-up, the truck then performs a sequence of pick-ups, treatments, and deliveries, and the route ends at the last delivery. From the truck perspective, the three actions of pick-up, treatment, and delivery can be performed in any order that respects the vehicle capacity of two and the route duration constraint, but for the single request, the three actions must be performed in the stated order. The problem is formulated as a mixed integer linear problem and several classes of valid inequalities are proposed and integrated into a branch-and-cut algorithm.

AB - In this study we present a branch-and-cut algorithm for a skip pick-up and delivery problem. The study is motivated by a real-life problem in which full skips are transported from waste drop-off stations to treatment facilities where they are emptied, and then brought back to the original drop-off station. The transportation of the skips is done by trucks with the capacity of carrying two containers at a time. The planning problem is to design the routes of the trucks that perform the collection to satisfy a number of requests in a planning period. A truck route starts at the first pick-up, the truck then performs a sequence of pick-ups, treatments, and deliveries, and the route ends at the last delivery. From the truck perspective, the three actions of pick-up, treatment, and delivery can be performed in any order that respects the vehicle capacity of two and the route duration constraint, but for the single request, the three actions must be performed in the stated order. The problem is formulated as a mixed integer linear problem and several classes of valid inequalities are proposed and integrated into a branch-and-cut algorithm.

KW - Branch-and-cut

KW - Pick-up and delivery problems

KW - Skip transport

KW - Transport

KW - Waste

U2 - 10.1016/j.cor.2024.106705

DO - 10.1016/j.cor.2024.106705

M3 - Journal article

AN - SCOPUS:85194298017

SN - 0305-0548

VL - 168

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 106705

ER -

A branch-and-cut algorithm for a skip pick-up and delivery problem

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this