IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i1d10.1007_s10878-022-00944-0.html
   My bibliography  Save this article

Approximation algorithms for some extensions of the maximum profit routing problem

Author

Listed:
  • Bogdan Armaselu

Abstract

In this paper, we consider extensions of the Maximum-Profit Public Transportation Route Planning Problem, or simply Maximum-Profit Routing Problem (MPRP), introduced in Armaselu and Daescu (Approximation algorithms for the maximum profit pick-up problem with time windows and capacity constraint, 2016. arXiv:1612.01038 , Interactive assisting framework for maximum profit routing in public transportation in smart cities, PETRA, 13–16, 2017). Specifically, we consider MPRP with Time-Variable Supply (MPRP-VS), in which the quantity $$q_i(t)$$ q i ( t ) supplied at site i is linearly increasing in time t, as opposed to the original MPRP problem, where the quantity is constant in time. For MPRP-VS, our main result is a $$5.5 \log {T} (1 + \epsilon ) \left( 1 + \frac{1}{1 + \sqrt{m}}\right) ^2$$ 5.5 log T ( 1 + ϵ ) 1 + 1 1 + m 2 approximation algorithm, where T is the latest time window and m is the number of vehicles used. We also study the MPRP with Multiple Vehicles per Site, in which a site may be visited by a vehicle multiple times, which can have 2 flavors: with quantities fixed in time (MPRP-M), and with time-variable quantities (MPRP-MVS). Our algorithmic solution to MPRP-VS can also improve upon the MPRP algorithm in Armaselu and Daescu (2017) under certain conditions. In addition, we simulate the MPRP-VS algorithm on a few benchmark, real-world, and synthetic instances.

Suggested Citation

  • Bogdan Armaselu, 2023. "Approximation algorithms for some extensions of the maximum profit routing problem," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-22, January.
    • Handle: RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00944-0
    DOI: 10.1007/s10878-022-00944-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-022-00944-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-022-00944-0?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. Marshall L. Fisher & Kurt O. Jörnsten & Oli B. G. Madsen, 1997. "Vehicle Routing with Time Windows: Two Optimization Algorithms," Operations Research, INFORMS, vol. 45(3), pages 488-492, June.
    2. Christos H. Papadimitriou & Mihalis Yannakakis, 1993. "The Traveling Salesman Problem with Distances One and Two," Mathematics of Operations Research, INFORMS, vol. 18(1), pages 1-11, February.
    3. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    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. 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.
    2. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    3. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    4. Meyer, Anne & Amberg, Boris, 2018. "Transport concept selection considering supplier milk runs – An integrated model and a case study from the automotive industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 147-169.
    5. Goel, Asvin & Meisel, Frank, 2013. "Workforce routing and scheduling for electricity network maintenance with downtime minimization," European Journal of Operational Research, Elsevier, vol. 231(1), pages 210-228.
    6. Klumpp, Matthias & Neukirchen, Thomas & Jäger, Stefanie, 2016. "Logistikqualifikation und Gamification: Der wissenschaftliche und fachpraktische Ansatz des Projektes MARTINA," ild Schriftenreihe 51, FOM Hochschule für Oekonomie & Management, Institut für Logistik- & Dienstleistungsmanagement (ild).
    7. Federico Della Croce, 2016. "MP or not MP: that is the question," Journal of Scheduling, Springer, vol. 19(1), pages 33-42, February.
    8. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2015. "Branch-and-Price for the Active-Passive Vehicle-Routing Problem," Working Papers 1513, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Paraskevopoulos, Dimitris C. & Laporte, Gilbert & Repoussis, Panagiotis P. & Tarantilis, Christos D., 2017. "Resource constrained routing and scheduling: Review and research prospects," European Journal of Operational Research, Elsevier, vol. 263(3), pages 737-754.
    10. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    11. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    12. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    13. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    14. Soares, Ricardo & Marques, Alexandra & Amorim, Pedro & Parragh, Sophie N., 2024. "Synchronisation in vehicle routing: Classification schema, modelling framework and literature review," European Journal of Operational Research, Elsevier, vol. 313(3), pages 817-840.
    15. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    16. Jörn Schönberger, 2017. "Scheduling constraints in dial-a-ride problems with transfers: a metaheuristic approach incorporating a cross-route scheduling procedure with postponement opportunities," Public Transport, Springer, vol. 9(1), pages 243-272, July.
    17. Martijn Ee & René Sitters, 2020. "The Chinese deliveryman problem," 4OR, Springer, vol. 18(3), pages 341-356, September.
    18. Ning-Rong Tao & Zu-Hua Jiang & Jian-Feng Liu & Bei-Xin Xia & Bai-He Li, 2019. "A Metaheuristic Algorithm to Transporter Scheduling for Assembly Blocks in a Shipyard considering Precedence and Cooperating Constraints," Discrete Dynamics in Nature and Society, Hindawi, vol. 2019, pages 1-14, January.
    19. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    20. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00944-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.