The opportunity cost of time window violations

Matteo Salani, Maria Battarra

Research output: Contribution to journalArticle

Abstract

This paper studies a variant of the vehicle routing problem with soft time windows (VRPSTW), inspired by real-world distribution problems. In applications, violations of the prescribed delivery time are commonly accepted. Customers’ inconvenience due to early or late arrival is typically modelled as a penalty cost included in the VRPSTW objective function, added to the routing costs. However, weighting routing costs against customer inconvenience is not straightforward for practitioners. In our problem definition, practitioners evaluate solutions by comparison with the hard time windows solution. The desired routing cost saving is set by the practitioners as a percentage of the nominal solution’s routing costs. The objective function minimizes the time window violations, or the customer inconvenience, with respect to the nominal solution. This allows practitioners to quantify the opportunity cost (i.e. the customer inconvenience), when a target routing cost saving is imposed. To solve the problem, we apply two exact algorithms: the first is based on a standard branch-and-cut-and-price (BCP), the second is a BCP nested in a bisection algorithm. Computational results demonstrate that the second algorithm outperforms the standard implementation. Solutions obtained with the opportunity cost interpretation of soft time windows are then compared with solutions obtained using both hard time windows and the standard interpretation of soft time windows.
LanguageEnglish
Pages343-361
Number of pages19
JournalEuro Journal on Transportation and Logistics
Volume7
Issue number4
Early online date3 Apr 2018
DOIs
StatusPublished - 1 Dec 2018

Fingerprint

opportunity costs
Time Windows
Costs
Routing
customer
Customers
costs
Branch-and-cut
Vehicle routing
Vehicle Routing Problem
Categorical or nominal
Objective function
interpretation
Bisection
time
Opportunity cost
Time windows
Violations
Exact Algorithms
weighting

Cite this

The opportunity cost of time window violations. / Salani, Matteo; Battarra, Maria.

In: Euro Journal on Transportation and Logistics, Vol. 7, No. 4, 01.12.2018, p. 343-361.

Research output: Contribution to journalArticle

@article{9b5c018785854843a72d3260125828bd,
title = "The opportunity cost of time window violations",
abstract = "This paper studies a variant of the vehicle routing problem with soft time windows (VRPSTW), inspired by real-world distribution problems. In applications, violations of the prescribed delivery time are commonly accepted. Customers’ inconvenience due to early or late arrival is typically modelled as a penalty cost included in the VRPSTW objective function, added to the routing costs. However, weighting routing costs against customer inconvenience is not straightforward for practitioners. In our problem definition, practitioners evaluate solutions by comparison with the hard time windows solution. The desired routing cost saving is set by the practitioners as a percentage of the nominal solution’s routing costs. The objective function minimizes the time window violations, or the customer inconvenience, with respect to the nominal solution. This allows practitioners to quantify the opportunity cost (i.e. the customer inconvenience), when a target routing cost saving is imposed. To solve the problem, we apply two exact algorithms: the first is based on a standard branch-and-cut-and-price (BCP), the second is a BCP nested in a bisection algorithm. Computational results demonstrate that the second algorithm outperforms the standard implementation. Solutions obtained with the opportunity cost interpretation of soft time windows are then compared with solutions obtained using both hard time windows and the standard interpretation of soft time windows.",
author = "Matteo Salani and Maria Battarra",
year = "2018",
month = "12",
day = "1",
doi = "10.1007/s13676-018-0121-3",
language = "English",
volume = "7",
pages = "343--361",
journal = "Euro Journal on Transportation and Logistics",
issn = "2192-4376",
publisher = "Springer Verlag",
number = "4",

}

TY - JOUR

T1 - The opportunity cost of time window violations

AU - Salani, Matteo

AU - Battarra, Maria

PY - 2018/12/1

Y1 - 2018/12/1

N2 - This paper studies a variant of the vehicle routing problem with soft time windows (VRPSTW), inspired by real-world distribution problems. In applications, violations of the prescribed delivery time are commonly accepted. Customers’ inconvenience due to early or late arrival is typically modelled as a penalty cost included in the VRPSTW objective function, added to the routing costs. However, weighting routing costs against customer inconvenience is not straightforward for practitioners. In our problem definition, practitioners evaluate solutions by comparison with the hard time windows solution. The desired routing cost saving is set by the practitioners as a percentage of the nominal solution’s routing costs. The objective function minimizes the time window violations, or the customer inconvenience, with respect to the nominal solution. This allows practitioners to quantify the opportunity cost (i.e. the customer inconvenience), when a target routing cost saving is imposed. To solve the problem, we apply two exact algorithms: the first is based on a standard branch-and-cut-and-price (BCP), the second is a BCP nested in a bisection algorithm. Computational results demonstrate that the second algorithm outperforms the standard implementation. Solutions obtained with the opportunity cost interpretation of soft time windows are then compared with solutions obtained using both hard time windows and the standard interpretation of soft time windows.

AB - This paper studies a variant of the vehicle routing problem with soft time windows (VRPSTW), inspired by real-world distribution problems. In applications, violations of the prescribed delivery time are commonly accepted. Customers’ inconvenience due to early or late arrival is typically modelled as a penalty cost included in the VRPSTW objective function, added to the routing costs. However, weighting routing costs against customer inconvenience is not straightforward for practitioners. In our problem definition, practitioners evaluate solutions by comparison with the hard time windows solution. The desired routing cost saving is set by the practitioners as a percentage of the nominal solution’s routing costs. The objective function minimizes the time window violations, or the customer inconvenience, with respect to the nominal solution. This allows practitioners to quantify the opportunity cost (i.e. the customer inconvenience), when a target routing cost saving is imposed. To solve the problem, we apply two exact algorithms: the first is based on a standard branch-and-cut-and-price (BCP), the second is a BCP nested in a bisection algorithm. Computational results demonstrate that the second algorithm outperforms the standard implementation. Solutions obtained with the opportunity cost interpretation of soft time windows are then compared with solutions obtained using both hard time windows and the standard interpretation of soft time windows.

U2 - 10.1007/s13676-018-0121-3

DO - 10.1007/s13676-018-0121-3

M3 - Article

VL - 7

SP - 343

EP - 361

JO - Euro Journal on Transportation and Logistics

T2 - Euro Journal on Transportation and Logistics

JF - Euro Journal on Transportation and Logistics

SN - 2192-4376

IS - 4

ER -