On Dynamical Situations in Vehicle Routing Problems (DSVRP)

Felix Makanjuola Aderibigbe; Kayode James Adebayo

doi:doi:10.11648/j.ajtte.20210601.11

| Peer-Reviewed

On Dynamical Situations in Vehicle Routing Problems (DSVRP)

Felix Makanjuola Aderibigbe, Kayode James Adebayo

Published in American Journal of Traffic and Transportation Engineering (Volume 6, Issue 1)

Received: 12 January 2020 Accepted: 21 January 2020 Published: 12 January 2021

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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), 2024. 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

Plain Text BibTeX RIS

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

Felix Makanjuola Aderibigbe

Department of Mathematics, Faculty of Science, Ekiti State University, Ado Ekiti, Nigeria
Kayode James Adebayo

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

Download PDF

Sections

Plain Text BibTeX RIS

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