Arc-Routing Models for Small-Package Local Routing

Si Chen (), Bruce Golden (), Richard Wong () and Hongsheng Zhong ()
Additional contact information
Si Chen: College of Business and Public Affairs, Murray State University, Murray, Kentucky 42071
Bruce Golden: R.H. Smith School of Business, University of Maryland, College Park, Maryland 20742
Richard Wong: United Parcel Service, Timonium, Maryland 21093
Hongsheng Zhong: United Parcel Service, Timonium, Maryland 21093

Transportation Science, 2009, vol. 43, issue 1, 43-55

Abstract: This paper studies the arc-routing problem that arises in small-package delivery. In practice, each service provider is encouraged to follow a master route---a predesigned sequence of street addresses---over an extended planning horizon (more than one day). The objective here is to construct efficient master routes. The focus on arc routing offers two advantages. First, real-world vehicle routing takes place over a street network, rather than in Euclidean space. Second, there are, typically, many fewer streets than customer locations. Currently, a deterministic arc-routing problem (DARP) model is used to solve the problem. However, this approach ignores the uncertainty in the street segment presence probability---the probability that a street segment requires (i.e., there is a demand for) a visit on a particular day. We introduce two new models, namely, the probabilistic arc-routing problem (PARP) model and the multiday arc-routing problem (MARP) model, which take into account the street segment presence probabilities. PARP attempts to minimize the expected length of the master route. It assumes that the street segment presence probabilities are independent. This model can require excessive amounts of computation time. On the other hand, MARP tries to minimize average length of the master route over prespecified days. This model can also be viewed as a Monte Carlo simulation approximation of the PARP. This approximation significantly reduces the computational burden. Additionally, by utilizing historical data, MARP incorporates real-world correlations among the street segment presence probabilities. Our computational results show that PARP and MARP may produce more efficient master routes than DARP by taking demand uncertainty into account.

Keywords: probabilistic arc routing; small-package local routing; vehicle routing (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1080.0255 (application/pdf)

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:inm:ortrsc:v:43:y:2009:i:1:p:43-55

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().