IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v301y2022i2p445-457.html
   My bibliography  Save this article

Scheduling activities with time-dependent durations and resource consumptions

Author

Listed:
  • Pottel, Steffen
  • Goel, Asvin

Abstract

In this paper we study the problem of scheduling a given sequence of activities where each activity consumes a resource with limited availability. Activity durations as well as resource consumptions are assumed to be time-dependent. Because of the interaction of time-dependent activity durations and resource consumptions, scheduling policies based on starting each activity in the sequence as early as possible may fail due to unnecessarily high resource consumptions exceeding the limited availability of the resource. We propose a dynamic discretization discovery algorithm that generates a partially time-expanded network during the search. We propose an acceleration technique allowing to significantly reduce the computational effort if the approach is embedded in an iterative solution procedure that frequently evaluates activity sequences which start with the same activities. Furthermore, we extend our approach to the case where resources can be replenished between subsequent activities. We evaluate our approach as a route evaluation method for the case of routing a fleet of electric vehicles in which travel durations and the energy consumed when travelling from one location to another depend on the time of the day.

Suggested Citation

  • Pottel, Steffen & Goel, Asvin, 2022. "Scheduling activities with time-dependent durations and resource consumptions," European Journal of Operational Research, Elsevier, vol. 301(2), pages 445-457.
  • Handle: RePEc:eee:ejores:v:301:y:2022:i:2:p:445-457
    DOI: 10.1016/j.ejor.2021.11.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721009838
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2021.11.032?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. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. Asvin Goel & Thibaut Vidal, 2014. "Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment," Transportation Science, INFORMS, vol. 48(3), pages 391-412, August.
    3. Min Zhang & Rajan Batta & Rakesh Nagi, 2009. "Modeling of Workflow Congestion and Optimization of Flow Routing in a Manufacturing/Warehouse Facility," Management Science, INFORMS, vol. 55(2), pages 267-280, February.
    4. Tilk, Christian & Goel, Asvin, 2020. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," European Journal of Operational Research, Elsevier, vol. 283(1), pages 108-124.
    5. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    6. Asvin Goel, 2009. "Vehicle Scheduling and Routing with Drivers' Working Hours," Transportation Science, INFORMS, vol. 43(1), pages 17-26, February.
    7. Asvin Goel, 2010. "Truck Driver Scheduling in the European Union," Transportation Science, INFORMS, vol. 44(4), pages 429-441, November.
    8. Kok, A.L. & Hans, E.W. & Schutten, J.M.J., 2011. "Optimizing departure times in vehicle routes," European Journal of Operational Research, Elsevier, vol. 210(3), pages 579-587, May.
    9. Thomas R. Visser & Remy Spliet, 2020. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(4), pages 1091-1112, July.
    10. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    11. Eric Prescott-Gagnon & Guy Desaulniers & Michael Drexl & Louis-Martin Rousseau, 2010. "European Driver Rules in Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 44(4), pages 455-473, November.
    12. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    13. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    14. Taş, Duygu & Gendreau, Michel & Jabali, Ola & Laporte, Gilbert, 2016. "The traveling salesman problem with time-dependent service times," European Journal of Operational Research, Elsevier, vol. 248(2), pages 372-383.
    15. Marie-Eve Rancourt & Jean-François Cordeau & Gilbert Laporte, 2013. "Long-Haul Vehicle Routing and Scheduling with Working Hour Rules," Transportation Science, INFORMS, vol. 47(1), pages 81-107, February.
    16. Samuel Pelletier & Ola Jabali & Gilbert Laporte, 2016. "50th Anniversary Invited Article—Goods Distribution with Electric Vehicles: Review and Research Perspectives," Transportation Science, INFORMS, vol. 50(1), pages 3-22, February.
    17. Goel, Asvin, 2018. "Legal aspects in road transport optimization in Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 144-162.
    18. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    19. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    20. Goel, Asvin, 2014. "Hours of service regulations in the United States and the 2013 rule change," Transport Policy, Elsevier, vol. 33(C), pages 48-55.
    21. Moritz Baum & Julian Dibbelt & Andreas Gemsa & Dorothea Wagner & Tobias Zündorf, 2019. "Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles," Transportation Science, INFORMS, vol. 53(6), pages 1627-1655, November.
    22. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    23. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    24. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    25. Claudia Archetti & Martin Savelsbergh, 2009. "The Trip Scheduling Problem," Transportation Science, INFORMS, vol. 43(4), pages 417-431, November.
    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. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    2. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    3. Asvin Goel & Thibaut Vidal & Adrianus Leendert Kok, 2021. "To team up or not: single versus team driving in European road freight transport," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 879-913, December.
    4. Christian Tilk & Asvin Goel, 2019. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," Working Papers 1914, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    5. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, May.
    6. Tilk, Christian & Goel, Asvin, 2020. "Bidirectional labeling for solving vehicle routing and truck driver scheduling problems," European Journal of Operational Research, Elsevier, vol. 283(1), pages 108-124.
    7. Eskandarzadeh, Saman & Fahimnia, Behnam, 2022. "Rest break policy comparison for heavy vehicle drivers in Australia," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    8. Daiane Maria Genaro Chiroli & Sérgio Fernando Mayerle & João Neiva Figueiredo, 2022. "Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints," Journal of Heuristics, Springer, vol. 28(1), pages 23-59, February.
    9. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    10. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    11. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    12. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    13. Pilz, Danny & Schwerdfeger, Stefan & Boysen, Nils, 2022. "Make or break: Coordinated assignment of parking space for breaks and rest periods in long-haul trucking," Transportation Research Part B: Methodological, Elsevier, vol. 164(C), pages 45-64.
    14. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    15. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    16. Goel, Asvin, 2018. "Legal aspects in road transport optimization in Europe," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 144-162.
    17. Mor, Andrea & Archetti, Claudia & Jabali, Ola & Simonetto, Alberto & Speranza, M. Grazia, 2022. "The Bi-objective Long-haul Transportation Problem on a Road Network," Omega, Elsevier, vol. 106(C).
    18. 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.
    19. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    20. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).

    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:ejores:v:301:y:2022:i:2:p:445-457. 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/eor .

    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.