IDEAS home Printed from https://ideas.repec.org/a/gam/jftint/v16y2024i2p64-d1340448.html
   My bibliography  Save this article

Online Optimization of Pickup and Delivery Problem Considering Feasibility

Author

Listed:
  • Ryo Matsuoka

    (Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan)

  • Koichi Kobayashi

    (Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan)

  • Yuh Yamashita

    (Graduate School of Information Science and Technoloty, Hokkaido University, Sapporo 060-0814, Japan)

Abstract

A pickup and delivery problem by multiple agents has many applications, such as food delivery service and disaster rescue. In this problem, there are cases where fuels must be considered (e.g., the case of using drones as agents). In addition, there are cases where demand forecasting should be considered (e.g., the case where a large number of orders are carried by a small number of agents). In this paper, we consider an online pickup and delivery problem considering fuel and demand forecasting. First, the pickup and delivery problem with fuel constraints is formulated. The information on demand forecasting is included in the cost function. Based on the orders, the agents’ paths (e.g., the paths from stores to customers) are calculated. We suppose that the target area is given by an undirected graph. Using a given graph, several constraints such as the moves and fuels of the agents are introduced. This problem is reduced to a mixed integer linear programming (MILP) problem. Next, in online optimization, the MILP problem is solved depending on the acceptance of orders. Owing to new orders, the calculated future paths may be changed. Finally, by using a numerical example, we present the effectiveness of the proposed method.

Suggested Citation

  • Ryo Matsuoka & Koichi Kobayashi & Yuh Yamashita, 2024. "Online Optimization of Pickup and Delivery Problem Considering Feasibility," Future Internet, MDPI, vol. 16(2), pages 1-15, February.
    • Handle: RePEc:gam:jftint:v:16:y:2024:i:2:p:64-:d:1340448
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1999-5903/16/2/64/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1999-5903/16/2/64/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. Hess, Alexander & Spinler, Stefan & Winkenbach, Matthias, 2021. "Real-time demand forecasting for an urban delivery platform," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    3. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2020. "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    4. Regue, Robert & Recker, Will, 2014. "Proactive vehicle routing with inferred demand to solve the bikesharing rebalancing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 192-209.
    5. Jun, Sungbum & Lee, Seokcheon & Yih, Yuehwern, 2021. "Pickup and delivery problem with recharging for material handling systems utilising autonomous mobile robots," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1153-1168.
    6. Denissa Sari Darmawi Purba & Eleftheria Kontou & Chrysafis Vogiatzis, 2021. "Evacuation Route Planning for Alternative Fuel Vehicles," Papers 2109.01578, arXiv.org, revised May 2022.
    Full references (including those not matched with items on IDEAS)

    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. Ouyang, Kechen & Wang, David Z.W., 2025. "Optimal operation strategies for freight transport with electric vehicles considering wireless charging lanes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    2. Zhang, Li & Liu, Zhongshan & Yu, Bin & Long, Jiancheng, 2024. "A ridesharing routing problem for airport riders with electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    3. Zhang, Li & Meng, Qiang & Wang, Hua & Yu, Bin, 2025. "Joint bus dispatching and bus bridging timetabling for mass rapid transit disruption management," Transportation Research Part B: Methodological, Elsevier, vol. 196(C).
    4. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    5. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    6. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    7. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Egan, Malcolm & Jakob, Michal, 2016. "Market mechanism design for profitable on-demand transport services," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 178-195.
    9. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    10. Jie Bao & Chengcheng Xu & Pan Liu & Wei Wang, 2017. "Exploring Bikesharing Travel Patterns and Trip Purposes Using Smart Card Data and Online Point of Interests," Networks and Spatial Economics, Springer, vol. 17(4), pages 1231-1253, December.
    11. Jiang, Zhoutong & Lei, Chao & Ouyang, Yanfeng, 2020. "Optimal investment and management of shared bikes in a competitive market," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 143-155.
    12. Zhenhua Chen & Qiong Chen & Yiying Chao & Cheng Xue, 2025. "Optimizing PHEV Routing with Hybrid Mode and Partial Charging via Labeling-Based Methods," Mathematics, MDPI, vol. 13(13), pages 1-20, June.
    13. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    14. Francis, Peter & Zhang, Guangming & Smilowitz, Karen, 2007. "Improved modeling and solution methods for the multi-resource routing problem," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1045-1059, August.
    15. Fagerholt, Kjetil, 2001. "Ship scheduling with soft time windows: An optimisation based approach," European Journal of Operational Research, Elsevier, vol. 131(3), pages 559-571, June.
    16. Jansen, Benjamin & Swinkels, Pieter C. J. & Teeuwen, Geert J. A. & van Antwerpen de Fluiter, Babette & Fleuren, Hein A., 2004. "Operational planning of a large-scale multi-modal transportation system," European Journal of Operational Research, Elsevier, vol. 156(1), pages 41-53, July.
    17. Le-Anh, T. & de Koster, M.B.M., 2004. "A Review Of Design And Control Of Automated Guided Vehicle Systems," ERIM Report Series Research in Management ERS;2004-030-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    18. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    19. Zheng, Jianfeng & Meng, Qiang & Sun, Zhuo, 2014. "Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design," European Journal of Operational Research, Elsevier, vol. 234(3), pages 874-884.
    20. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2008. "The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments," European Journal of Operational Research, Elsevier, vol. 185(2), pages 534-551, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    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:gam:jftint:v:16:y:2024:i:2:p:64-:d:1340448. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.