An exact algorithm for a rich vehicle routing problem with private fleet and common carrier

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.

Original languageEnglish
Pages (from-to)986-1000
Number of pages15
JournalTransportation Science
Volume53
Issue number4
DOIs
Publication statusPublished - 4 Aug 2019

Fingerprint

common carrier
Vehicle routing
customer
costs
Costs
cost structure
outsourcing
heuristics
Outsourcing
demand
literature

Keywords

  • Common carriers
  • Exact algorithms
  • Private fleet
  • Vehicle routing

Cite this

@article{a0c2ea4bd5324433861ea35fcea3874a,
title = "An exact algorithm for a rich vehicle routing problem with private fleet and common carrier",
abstract = "The vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.",
keywords = "Common carriers, Exact algorithms, Private fleet, Vehicle routing",
author = "Said Dabia and David Lai and Daniele Vigo",
year = "2019",
month = "8",
day = "4",
doi = "10.1287/trsc.2018.0852",
language = "English",
volume = "53",
pages = "986--1000",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

An exact algorithm for a rich vehicle routing problem with private fleet and common carrier. / Dabia, Said; Lai, David; Vigo, Daniele.

In: Transportation Science, Vol. 53, No. 4, 04.08.2019, p. 986-1000.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - An exact algorithm for a rich vehicle routing problem with private fleet and common carrier

AU - Dabia, Said

AU - Lai, David

AU - Vigo, Daniele

PY - 2019/8/4

Y1 - 2019/8/4

N2 - The vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.

AB - The vehicle routing problem with private fleet and common carrier (VRPPC) is a generalization of the classical vehicle routing problem in which the owner of a private fleet can either visit a customer with one of the owner's vehicles or assign the customer to a common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economically convenient to do so. The owner's objective is to minimize the variable and fixed costs for operating the owner's fleet plus the total cost charged by the common carrier. This family of problems has many practical applications, particularly in the design of last-mile distribution services and has received some attention in the literature, in which some heuristics were proposed. We extend here the VRPPC by considering more realistic cost structures that account for quantity discounts on outsourcing costs and by considering time windows resulting in a rich VRPPC (RVRPPC). We present an exact approach based on a branch-and-cut-and-price algorithm for the RVRPPC and test the algorithm on instances from the literature.

KW - Common carriers

KW - Exact algorithms

KW - Private fleet

KW - Vehicle routing

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

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

U2 - 10.1287/trsc.2018.0852

DO - 10.1287/trsc.2018.0852

M3 - Article

VL - 53

SP - 986

EP - 1000

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 4

ER -