IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v209y2019icp194-204.html
   My bibliography  Save this article

Optimal delivery of two similar products to N ordered customers with product preferences

Author

Listed:
  • Kyriakidis, Epaminondas G.
  • Dimitrakos, Theodosis D.
  • Karamatsoukis, Constantinos C.

Abstract

We study a mathematical model for a specific vehicle routing problem in which a vehicle starts its route from a depot loaded with items of two similar but not identical products. The vehicle must deliver the products to N customers according to a predefined sequence. It is assumed that each customer prefers either product 1 or product 2 with known probabilities and the quantity that each customer demands is a random variable with known distribution. The actual preference and demand of each customer are revealed upon the vehicle's arrival at customer's site. The demand of each customer cannot exceed the vehicle capacity and the vehicle is allowed during its route to return to the depot to restock with quantities of both products. The travel costs between consecutive customers and the travel costs between the customers and the depot are known. If there is shortage for the desired product it is permitted to deliver the other product at a reduced price. The optimal routing strategy is found by implementing a suitable stochastic dynamic programming algorithm. It is possible to prove that the optimal routing strategy has a specific threshold-type structure. Furthermore, if we consider the same problem without the assumption that the customers are ordered, numerical experiments indicate that the optimal routing strategy can be computed for N≤8.

Suggested Citation

  • Kyriakidis, Epaminondas G. & Dimitrakos, Theodosis D. & Karamatsoukis, Constantinos C., 2019. "Optimal delivery of two similar products to N ordered customers with product preferences," International Journal of Production Economics, Elsevier, vol. 209(C), pages 194-204.
    • Handle: RePEc:eee:proeco:v:209:y:2019:i:c:p:194-204
    DOI: 10.1016/j.ijpe.2017.12.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527317304231
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2017.12.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Pandelis, D.G. & Kyriakidis, E.G. & Dimitrakos, T.D., 2012. "Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands," European Journal of Operational Research, Elsevier, vol. 217(2), pages 324-332.
    3. Dimitrakos, T.D. & Kyriakidis, E.G., 2015. "A single vehicle routing problem with pickups and deliveries, continuous random demands and predefined customer order," European Journal of Operational Research, Elsevier, vol. 244(3), pages 990-993.
    4. Cortés, Cristián E. & Gendreau, Michel & Rousseau, Louis Martin & Souyris, Sebastián & Weintraub, Andrés, 2014. "Branch-and-price and constraint programming for solving a real-life technician dispatching problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 300-312.
    5. Segerstedt, Anders, 2014. "A simple heuristic for vehicle routing – A variant of Clarke and Wright's saving method," International Journal of Production Economics, Elsevier, vol. 157(C), pages 74-79.
    6. U Derigs & K Reuter, 2009. "A simple and efficient tabu search heuristic for solving the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1658-1669, December.
    7. Jiang, J. & Ng, K.M. & Teo, K.M., 2016. "Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A," European Journal of Operational Research, Elsevier, vol. 248(2), pages 404-414.
    8. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    9. Minis, I. & Tatarakis, A., 2011. "Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence," European Journal of Operational Research, Elsevier, vol. 213(1), pages 37-51, August.
    10. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    11. Goetschalckx, Marc & Jacobs-Blecha, Charlotte, 1989. "The vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 42(1), pages 39-51, September.
    12. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    13. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    14. Kritikos, Manolis N. & Ioannou, George, 2013. "The heterogeneous fleet vehicle routing problem with overloads and time windows," International Journal of Production Economics, Elsevier, vol. 144(1), pages 68-75.
    15. Tsirimpas, P. & Tatarakis, A. & Minis, I. & Kyriakidis, E.G., 2008. "Single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 187(2), pages 483-495, June.
    16. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    17. Tatarakis, A. & Minis, I., 2009. "Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 197(2), pages 557-571, September.
    18. Pandelis, D.G. & Karamatsoukis, C.C. & Kyriakidis, E.G., 2013. "Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery," European Journal of Operational Research, Elsevier, vol. 231(3), pages 577-586.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos & Constantinos C. Karamatsoukis, 2020. "A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1559-1582, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos & Constantinos C. Karamatsoukis, 2020. "A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1559-1582, December.
    2. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    3. Zhu, Lin & Sheu, Jiuh-Biing, 2018. "Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 271(3), pages 896-912.
    4. Dimitrakos, T.D. & Kyriakidis, E.G., 2015. "A single vehicle routing problem with pickups and deliveries, continuous random demands and predefined customer order," European Journal of Operational Research, Elsevier, vol. 244(3), pages 990-993.
    5. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2018. "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 193-221, September.
    6. Pandelis, D.G. & Karamatsoukis, C.C. & Kyriakidis, E.G., 2013. "Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery," European Journal of Operational Research, Elsevier, vol. 231(3), pages 577-586.
    7. Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
    8. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    9. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    10. Goodson, Justin C., 2015. "A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 241(2), pages 361-369.
    11. F. Hooshmand Khaligh & S.A. MirHassani, 2016. "A mathematical model for vehicle routing problem under endogenous uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 579-590, January.
    12. Minis, I. & Tatarakis, A., 2011. "Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence," European Journal of Operational Research, Elsevier, vol. 213(1), pages 37-51, August.
    13. Jin, Ming & Li, Gang & Cheng, T.C.E., 2018. "Buy online and pick up in-store: Design of the service area," European Journal of Operational Research, Elsevier, vol. 268(2), pages 613-623.
    14. Jorge E. Mendoza & Bruno Castanier & Christelle Guéret & Andrés L. Medaglia & Nubia Velasco, 2011. "Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 45(3), pages 346-363, August.
    15. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    16. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    17. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    18. Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2010. "The Vehicle Routing Problem with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 44(4), pages 474-492, November.
    19. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    20. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.

    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:eee:proeco:v:209:y:2019:i:c:p:194-204. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    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.