Ensuring service levels in routing problems with time windows and stochastic travel times

Jan Fabian Ehmke, Ann Melissa Campbell and Timothy L. Urban

European Journal of Operational Research, 2015, vol. 240, issue 2, 539-550

Abstract: In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings.

Keywords: Transportation; Vehicle routing; Stochastic travel times; Service level; Chance constraint (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714005487
Full text for ScienceDirect subscribers only

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:eee:ejores:v:240:y:2015:i:2:p:539-550

DOI: 10.1016/j.ejor.2014.06.045

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().