IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v62y2011i10p1827-1843.html
   My bibliography  Save this article

Pickup and delivery network segmentation using contiguous geographic clustering

Author

Listed:
  • A I Jarrah

    (The George Washington University, Washington, DC, USA)

  • J F Bard

    (The University of Texas, Austin, USA)

Abstract

This paper addresses the problem of partitioning a local service region into nonoverlapping work areas in which pickups and deliveries are made throughout the day. For a fleet of homogeneous vehicles, a given set of customers, and expected demand for service, the objective is to find the least number of work areas or clusters that satisfy a variety of geometric and capacity constraints. Using rectangles as the basic shape, each cluster must have an aspect ratio that falls within certain bounds, as well as meet load and time requirements dictated by the capacity of a vehicle and the working hours in a day, respectively. The latter requirement presents a unique hurdle because travel times are a function of the actual routes followed by the drivers, and are not known, even in a probabilistic sense, until the clusters are formed. A novel aspect of the paper is the method proposed for dealing with this uncertainty. The problem is modelled using a compact set-covering formulation and is solved with an adaptive column generation heuristic. Because it is not possible to efficiently represent all the constraints in algebraic form, thus allowing a Dantzig-Wolfe decomposition, a constructive approach was taken. The first step involved generating a subset of attractive clusters from seed customers scattered throughout the service region and then iteratively pricing them out to obtain a relaxed solution to the set-covering model. To find integer solutions, a three-phase variable fixing scheme was designed with the aim of balancing solution quality with runtimes. The full methodology was tested on six data sets provided by an internationally known express package carrier. The results showed that vehicle reductions averaging 7.6% could be realized by adopting the configurations derived from the proposed approach.

Suggested Citation

  • A I Jarrah & J F Bard, 2011. "Pickup and delivery network segmentation using contiguous geographic clustering," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(10), pages 1827-1843, October.
  • Handle: RePEc:pal:jorsoc:v:62:y:2011:i:10:p:1827-1843
    as

    Download full text from publisher

    File URL: http://www.palgrave-journals.com/jors/journal/v62/n10/pdf/jors2010123a.pdf
    File Function: Link to full text PDF
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: http://www.palgrave-journals.com/jors/journal/v62/n10/full/jors2010123a.html
    File Function: Link to full text HTML
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Meiyan Lin & Kwai Sang Chin & Lijun Ma & Kwok Leung Tsui, 2020. "A comprehensive multi-objective mixed integer nonlinear programming model for an integrated elderly care service districting problem," Annals of Operations Research, Springer, vol. 291(1), pages 499-529, August.
    2. Bard, Jonathan F. & Jarrah, Ahmad I., 2013. "Integrating commercial and residential pickup and delivery networks: A case study," Omega, Elsevier, vol. 41(4), pages 706-720.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:62:y:2011:i:10:p:1827-1843. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.