| Peer-Reviewed

On Dynamical Situations in Vehicle Routing Problems (DSVRP)

Received: 12 January 2020     Accepted: 21 January 2020     Published: 12 January 2021
Views:       Downloads:
Abstract

This paper discusses the formulation of a stochastic Vehicle Routing Problem (VRP) process, introduced to existing deterministic VRP process, directing all efforts towards the dynamical situations that occur in a typical VRP setting as it applies to everyday real-life situations. It contrasts the dichotomy between static and dynamical situations in VRP, constructs and analyzes the relationship between static and dynamical situations in Vehicle Routing Problems, formulates an expression to describe the dynamical situation in VRP and relates the problem formulation to existing VRP with a view to solving the problem as it applies to real-life situations, a major trend in the business world today. With a view to achieving these, this paper associates the merits of reactivation of route, re-optimization of operation process and projects an anticipatory demand for a dynamical situation in VRP with stochastic requests via three stages: Pre-Decision States, Decisions States and Post-Decision States. First, as a reaction to anticipatory customers’ requests, the current routing plans need to be re-optimized and current customers’ request reactivated. Second, potential future requests need to be anticipated along current decision making since life itself is dynamic. Decisions need to be made in good time. Though, the limited time frame between when a vehicle leaves and returns to the depot often prohibits extensive optimization in both dimensions rather, answer the questions that arise on how to utilize the limited time effectively and judiciously, satisfying both the current and anticipatory customers equally.

Published in American Journal of Traffic and Transportation Engineering (Volume 6, Issue 1)
DOI 10.11648/j.ajtte.20210601.11
Page(s) 1-9
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2021. Published by Science Publishing Group

Keywords

Dynamical Situation, Static Situation, Vehicle Routing Problem, Re-optimization, Anticipatory Routing, Stochastic Demand, Pre-Decision State, Post-Decision State

References
[1] Jean-Francois, C., Gilbert, L., Martin W. P. S. and Daniele, V., (2007), Vehicle Routing, Handbook on OR and MS, Vol. 14, pg. 367-427.
[2] Christofides, N., Mingozzi, A. and Toth, P., (1976), Combinatorial Optimization, John Wiley & Sons.
[3] Malkhi, D., Nisan, N., Pinkas, B. and Sella, Y., (2004), Fairplay - a Secure Two-party Computation System, Proceedings of the thirteenth USENIX Security Symposium, pp. 287–302.
[4] Zaepfel, G. and Boegl, M., (2008), Multi-period Vehicle Routing and Crew Scheduling with Outsourcing Options. International Journal of Production Economics, 113 (2): 980–996.
[5] Du, T., Wang, F. K., and Lu, P. Y., (2007), A Real-time Vehicle-dispatching System for Consolidating Milk Runs. Transportation Research Part E: Logistics and Transportation Review, 43 (5): 565–577.
[6] Gendreau, M., Guertin, F., Potvin, J. Y., and Seguin, R., (2006), Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pickups and Deliveries. Transportation Research Part C: Emerging Technologies, 14 (3): 157–174.
[7] Larsen, A., (2000), The dynamic vehicle routing problem. Kgs. Lyngby, Denmark: Technical University of Denmark (DTU), IMM-Ph. D., No. 2000-73.
[8] Brotcorne, L., Laporte, G., and Semet, F., (2003), Ambulance Location and Relocation Models. European Journal of Operational Research, 147 (3): 451–463.
[9] Dantzig, G. and Ramser, J., (1959), The Truck Dispatching Problem, Management Science, 6 (1): 80–91.
[10] Hvattum, L. M., Lokketangen, A., Laporte, G., (2006), Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic, Transportation Science, 40 (4): 421–438.
[11] Gendreau, M., Potvin, J.-Y., Braysy, O., Hasle, G., and Lokketangen, A., (2008), Metaheuristics for the Vehicle Routing Problem and its Extensions: Latest Advances and New Challenges, pages 143–169. Springer.
[12] Psaraftis, H. N., Wen, M. and Kontovas, C. A., (2016), Dynamic Vehicle Routing Problems: Three Decades and Counting. Networks, 67 (1): 3–31.
[13] Zhang, S., Ohlmann, J. W. and Thomas, B. W., (2018), Dynamic Orienteering on a Network of Queues, Transportation Science, 52 (3): 691–706.
[14] Goodson, J. C., Thomas, B. W. and Ohlmann, J. W., (2015), Restocking-based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration limits. Transportation Science, 50 (2): 591–607.
[15] Schilde, M., Doerner, K. F. and Hart, R. F., (2014), Integrating Stochastic Time-dependent Travel Speed in Solution Methods for the Dynamic Dial-a-ride Problem. European Journal of Operational Research, 238 (1): 18–30.
[16] Speranza, M. G., (2018), Trends in Transportation and Logistics. European Journal of Operational Research, 264 (3): 830-836.
[17] Mitrovi´c-Mini´c, S., Krishnamurti, R., Laporte, G., (2004), Double Horizon-based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows. Transportation Research Part B, 38 (8): 669–685.
[18] Branke, J., Middendorf, M., Noeth, G., and Dessouky, M., (2005), Waiting Strategies for Dynamic Vehicle Routing. Transportation Science, 39 (3): 298–312.
[19] Pureza, V., Laporte, G., (2008), Waiting and Buffering Strategies for the Dynamic Pickup and Delivery Problem with Time Windows. INFOR, 46 (3): 165–175.
[20] Jergensen, C., (1997), Driftsoptimering pa kraftvarmesystemer. 290 pp.
[21] Larsen, A., Madsen, O. B. G. and Solomon, M. M., (2002), Partially Dynamic Vehicle Routing-models and Algorithms. Journal of the Operational Research Society, 53 (6): 637–646.
[22] Ritzinger, U., Puchinger, J. and Hartl, R. F., (2014), Dynamic Programming Based Metaheuristics for the Dial-a-ride Problem. Annals of Operations Research, pages 1–18.
[23] Ehmke, J. F. and Campbell, A. M., (2014), Customer Acceptance Mechanisms for Home Deliveries in Metropolitan Areas. European Journal of Operational Research, 233 (1): 193–207.
[24] Maxwell, M. S., Restrepo, M., Henderson, S. G. and Topaloglu, H., (2010), Approximate dynamic programming for Ambulance Redeployment, INFORMS Journal on Computing, 22 (2): 266–38.
[25] Thomas, B. W., (2007), Waiting Strategies for Anticipating Service Requests from Known Customer Locations. Transportation Science, 41 (3): 319–331.
[26] Voccia, S. A., Campbell, A. M. and Thomas, B. W., (2018), The Same-day Delivery Problem for Online Purchases. Transportation Science.
[27] Brinkmann, J., Ulmer, M. W. and Mattfeld, D. C., (2015), Short-term Strategies for Stochastic Inventory Routing in Bike Sharing Systems. Transportation Research Procedia, 10: 364–373.
[28] Ulmer, M. W., (2017), Approximate Dynamic Programming for Dynamic Vehicle Routing. Operations Research/Computer Science Interfaces Series. Springer.
[29] Puterman, M. L., (2014), Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York.
[30] Russell, R. A. and Chiang, W. C., (2006), Scatter Search for the Vehicle Routing Problem with Time Windows, European Journal of Operational Research, 169 (2): 606–622.
[31] Adebayo, K. J., Aderibigbe, F. M. and Dele-Rotimi, A. O., (2019) On Vehicle Routing Problems (VRP) with a Focus on Multiple Priorities. American Journal of Computational Mathematics, 9, 348-357.
[32] Miller, D. L., Pekny, J. F., (1995), A Staged Primal-dual Algorithm for Perfect B-matching with Edge Capacities. ORSA Journal on Computing 7, 298–320.
[33] Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M., and Soumis, F., (1999), 2-path Cuts for the Vehicle Routing Problem with Time Windows, Transportation Science 33: 101-116.
Cite This Article
  • APA Style

    Felix Makanjuola Aderibigbe, Kayode James Adebayo. (2021). On Dynamical Situations in Vehicle Routing Problems (DSVRP). American Journal of Traffic and Transportation Engineering, 6(1), 1-9. https://doi.org/10.11648/j.ajtte.20210601.11

    Copy | Download

    ACS Style

    Felix Makanjuola Aderibigbe; Kayode James Adebayo. On Dynamical Situations in Vehicle Routing Problems (DSVRP). Am. J. Traffic Transp. Eng. 2021, 6(1), 1-9. doi: 10.11648/j.ajtte.20210601.11

    Copy | Download

    AMA Style

    Felix Makanjuola Aderibigbe, Kayode James Adebayo. On Dynamical Situations in Vehicle Routing Problems (DSVRP). Am J Traffic Transp Eng. 2021;6(1):1-9. doi: 10.11648/j.ajtte.20210601.11

    Copy | Download

  • @article{10.11648/j.ajtte.20210601.11,
      author = {Felix Makanjuola Aderibigbe and Kayode James Adebayo},
      title = {On Dynamical Situations in Vehicle Routing Problems (DSVRP)},
      journal = {American Journal of Traffic and Transportation Engineering},
      volume = {6},
      number = {1},
      pages = {1-9},
      doi = {10.11648/j.ajtte.20210601.11},
      url = {https://doi.org/10.11648/j.ajtte.20210601.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajtte.20210601.11},
      abstract = {This paper discusses the formulation of a stochastic Vehicle Routing Problem (VRP) process, introduced to existing deterministic VRP process, directing all efforts towards the dynamical situations that occur in a typical VRP setting as it applies to everyday real-life situations. It contrasts the dichotomy between static and dynamical situations in VRP, constructs and analyzes the relationship between static and dynamical situations in Vehicle Routing Problems, formulates an expression to describe the dynamical situation in VRP and relates the problem formulation to existing VRP with a view to solving the problem as it applies to real-life situations, a major trend in the business world today. With a view to achieving these, this paper associates the merits of reactivation of route, re-optimization of operation process and projects an anticipatory demand for a dynamical situation in VRP with stochastic requests via three stages: Pre-Decision States, Decisions States and Post-Decision States. First, as a reaction to anticipatory customers’ requests, the current routing plans need to be re-optimized and current customers’ request reactivated. Second, potential future requests need to be anticipated along current decision making since life itself is dynamic. Decisions need to be made in good time. Though, the limited time frame between when a vehicle leaves and returns to the depot often prohibits extensive optimization in both dimensions rather, answer the questions that arise on how to utilize the limited time effectively and judiciously, satisfying both the current and anticipatory customers equally.},
     year = {2021}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - On Dynamical Situations in Vehicle Routing Problems (DSVRP)
    AU  - Felix Makanjuola Aderibigbe
    AU  - Kayode James Adebayo
    Y1  - 2021/01/12
    PY  - 2021
    N1  - https://doi.org/10.11648/j.ajtte.20210601.11
    DO  - 10.11648/j.ajtte.20210601.11
    T2  - American Journal of Traffic and Transportation Engineering
    JF  - American Journal of Traffic and Transportation Engineering
    JO  - American Journal of Traffic and Transportation Engineering
    SP  - 1
    EP  - 9
    PB  - Science Publishing Group
    SN  - 2578-8604
    UR  - https://doi.org/10.11648/j.ajtte.20210601.11
    AB  - This paper discusses the formulation of a stochastic Vehicle Routing Problem (VRP) process, introduced to existing deterministic VRP process, directing all efforts towards the dynamical situations that occur in a typical VRP setting as it applies to everyday real-life situations. It contrasts the dichotomy between static and dynamical situations in VRP, constructs and analyzes the relationship between static and dynamical situations in Vehicle Routing Problems, formulates an expression to describe the dynamical situation in VRP and relates the problem formulation to existing VRP with a view to solving the problem as it applies to real-life situations, a major trend in the business world today. With a view to achieving these, this paper associates the merits of reactivation of route, re-optimization of operation process and projects an anticipatory demand for a dynamical situation in VRP with stochastic requests via three stages: Pre-Decision States, Decisions States and Post-Decision States. First, as a reaction to anticipatory customers’ requests, the current routing plans need to be re-optimized and current customers’ request reactivated. Second, potential future requests need to be anticipated along current decision making since life itself is dynamic. Decisions need to be made in good time. Though, the limited time frame between when a vehicle leaves and returns to the depot often prohibits extensive optimization in both dimensions rather, answer the questions that arise on how to utilize the limited time effectively and judiciously, satisfying both the current and anticipatory customers equally.
    VL  - 6
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics, Faculty of Science, Ekiti State University, Ado Ekiti, Nigeria

  • Department of Mathematics, Faculty of Science, Ekiti State University, Ado Ekiti, Nigeria

  • Sections