A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities

Andrea Bettinelli, Valentina Cacchiani, Teodor Gabriel Crainic, Daniele Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.

Original languageEnglish
Pages (from-to)824-839
Number of pages16
JournalEuropean Journal of Operational Research
Volume279
Issue number3
DOIs
Publication statusPublished - 16 Dec 2019

Fingerprint

Pickup and Delivery
Branch-and-cut
Pickups
Time Windows
Customers
Costs
Distribution Center
Column Generation
Time windows
Pickup and delivery
Dynamic programming
Exact Algorithms
Logistics
Pricing
Dynamic Programming
Penalty
Routing
Benchmark
Subset

Keywords

  • Bi-directional dynamic programming
  • Branch-and-Cut-and-Price
  • Routing
  • Separate Pickup and Delivery Problem

Cite this

@article{1db68f8e1e974eb7b261302a844fb5f3,
title = "A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities",
abstract = "We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.",
keywords = "Bi-directional dynamic programming, Branch-and-Cut-and-Price, Routing, Separate Pickup and Delivery Problem",
author = "Andrea Bettinelli and Valentina Cacchiani and Crainic, {Teodor Gabriel} and Daniele Vigo",
year = "2019",
month = "12",
day = "16",
doi = "10.1016/j.ejor.2019.06.032",
language = "English",
volume = "279",
pages = "824--839",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities. / Bettinelli, Andrea; Cacchiani, Valentina; Crainic, Teodor Gabriel; Vigo, Daniele.

In: European Journal of Operational Research, Vol. 279, No. 3, 16.12.2019, p. 824-839.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities

AU - Bettinelli, Andrea

AU - Cacchiani, Valentina

AU - Crainic, Teodor Gabriel

AU - Vigo, Daniele

PY - 2019/12/16

Y1 - 2019/12/16

N2 - We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.

AB - We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.

KW - Bi-directional dynamic programming

KW - Branch-and-Cut-and-Price

KW - Routing

KW - Separate Pickup and Delivery Problem

UR - http://www.scopus.com/inward/record.url?scp=85068836298&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068836298&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2019.06.032

DO - 10.1016/j.ejor.2019.06.032

M3 - Article

VL - 279

SP - 824

EP - 839

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -