Vehicle Routing Problem in Competitive Environment: Two-Person Nonzero Sum Game Approach

Document Type : Research Paper

Authors

1 Industrial Engineering Department, Azad University Tehran South Branch, Tehran

2 Department of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran

3 Islamic Azad University-South Tehran Branch, Tehran-Iran

Abstract

Vehicle routing problem is one of the most important issues in transportation. Among VRP problems, the competitive VRP is more important because there is a tough competition between distributors and retailers. In this study we introduced new method for VRP in competitive environment. In these methods Two-Person Nonzero Sum games are defined to choose equilibrium solution. Therefore, revenue given in each route is different. In this paper, two distributors has been considered in a city with a set of customers and the best route with maximum revenue has been determined. First we introduced the Hawk-Dove procedure for the VRP problem and then by using Nash bargaining model the equilibrium strategy of the game is calculated. The result of this method is different based on the kind of the strategy that each distributor chooses. In the Hawk-Dove game, if both of distributors choose the Dove procedure, they will get equal but less revenue. In the Nash Bargaining Game, the equilibrium strategy will obtained when distance of revenues of both distributors form its breakdown payoff is maximum.

Keywords

Main Subjects

References

AHMED E., A. S. HEGAZI, A. S. ELGAZZAR. (2002) “ON SPATIAL ASYMMETRIC GAMES”. Advances in Complex Systems A Multidisciplinary Journal, 5(4):433.
Alaei, S., & Setak, M., (1888). “DESIGNING OF SUPPLY CHAIN COORDINATION MECHANISM WITH LEADERSHIP CONSIDERING (RESEARCH NOTE)”. International Journal of Engineering-Transactions C: Aspects, 27(12).
Alexander, J., Skyrms, B. (1999). “Bargaining with neighbors: Is justice contagious?”. The Journal of philosophy, 588-598.
Altman, E., ElAzouzi, R., Hayel, Y., Tembine, H. (2008) “An evolutionary game approach for the design of congestion control protocols in wireless networks”.  Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, p: 547 – 552.
Asher, D.E. ; Zaldivar, A. ; Barton, B. ; Brewer, A.A (2012) “Reciprocity and Retaliation in Social Games With Adaptive Agents. Autonomous Mental Development”, IEEE Transactions. 4(3): 226 – 238.
Baldacci, R., Mingozzi, A., Roberti, R. (2012). “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints”. European Journal of Operational Research, 218(1), 1-6.
Barron, E.N., (2013) “Game Theory: an introduction”, 2nd edition.
Binmore, K., Rubinstein, A., Wolinsky, A., (1986). “The Nash bargaining solution in economic modeling”, The RAND Journal of Economics 17 (2), pp. 176–188.
Bramoullé Y. (2001) Complementarily and Social Networks. French Ministry of Agriculture and the University of Maryland.
Braysy O, Gendreau M. (2005) “Vehicle routing problem with time windows, part I: route construction and local search algorithms”. Transportation Science;39:104–18.
Cantrell R.S. and Cosner C. (2004) “Deriving reaction–diffusion models in ecology from interacting particle systems”. Journal of Mathematical Biology, 48(2): 187-217.
Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F, (2002) “The VRP with time windows. In: Toth P, Vigo D, editors. The vehicle routing problem”, SIAM Monographs on Discrete Mathematics and Applications, Vol. 9, Philadelphia, PA; p. 157–194.
Courtene-Jones, W., & Briffa, M. (2014). “Boldness and asymmetric contests: role-and outcome-dependent effects of fighting in hermit crabs”. Behavioral Ecology, aru085.
Crowley P.H. (2000) “Hawks, Doves, and Mixed-symmetry Games”.  Journal of Theoretical Biology, 204(4): 543–563.
Dantzig, George Bernard and Ramser, John Hubert (1959), “The Truck Dispatching Problem”. Management Science 6 (1): 80–91.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & ROUSSEAU, L. (2013). “The vehicle routing problem with hard time windows and stochastic service times”. Cahier du GERAD, G-2013-45.
Fakhrzada, M. B., & Esfahanib, A. S. (2014). “Modeling the Time Windows Vehicle Routing Problem in Cross-docking Strategy Using Two Meta-heuristic Algorithms”, International Journal of Engineering-TRANSACTIONS A: Basics, 27(7), 1113-1126.
Flisberg, P., Frisk, M., Rönnqvist, M., & Guajardo, M. (2015). “Potential savings and cost allocations for forest fuel transportation in Sweden: A country-wide study”. Energy, 85, 353-365.
Geiger MJ., (2003). “Multi-criteria und Fuzzy Systeme in Theorie und Praxis. In: A computational study of genetic crossover operators for multi-objective vehicle routing problem with soft time windows”. Deutscher Universities-Verlag; p. 191–207.
Golden, B. L., & Assad, A. A. (1988). “Vehicle Routing: Methods and Studies”, volume 16 of Studies in Management Science and Systems.
Kellner, F. (2016). Allocating greenhouse gas emissions to shipments in road freight transportation: Suggestions for a global carbon accounting standard. Energy Policy, 98, 565-575.
Ko, Y. D. (2016). An airline's management strategies in a competitive air transport market. Journal of Air Transport Management, 50, 53-61.
Hafezalkotob, A., Babaei, M. S., Rasulibaghban, A., Noori-daryan, M. (2014). “Distribution Design of Two Rival Decenteralized Supply Chains: a Two-person Nonzero Sum Game Theory Approach”. International Journal of Engineering-Transactions B: Applications, 27(8), 1233-1242.
Helbing D. (2009) “Pattern formation, social forces, and diffusion instability in games with success-driven motion”. The European Physical Journal B, 67(3): 345-356.
Hernandez, F., Feillet, D., Giroudeau, R., & Naud, O. (2016). “Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows”. European Journal of Operational Research, 249(2), 551-559.
Liao, C. H., & Chen, C. W. (2015). “Use of Advanced Traveler Information Systems for Route Choice: Interpretation Based on a Bayesian Model”. Journal of Intelligent Transportation Systems, 19(3), 316-325.
Li, X., Tian, P., & Leung, S. C. (2010). “Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm”. International Journal of Production Economics, 125(1), 137-145.
LIU Wei-bing and WANG Xian-jia (2007) “Study on evolutionary games based on PSO-neural networks”. Systems Engineering and Electronics.
Mahmoudi, R., Hafezalkotob, A., Makui, A. (2014). “Source selection problem of competitive power plants under government intervention: a game theory approach”. Journal of Industrial Engineering International, 10(3), 1-15.
Melián-Batista, B., De Santiago, A., AngelBello, F., & Alvarez, A. (2014). “A bi-objective vehicle routing problem with time windows: a real case in Tenerife”. Applied Soft Computing, 17, 140-152.
Nash  JF, (1950). “The  bargaining problem”. Econometrica; 18 (2), 155-162.
Ombuki, B., Ross, B. J., & Hanshar, F. (2006). “Multi-objective genetic algorithms for vehicle routing problem with time windows”. Applied Intelligence,24(1), 17-30.
Pedersen P. (2003) “Moral Hazard in Traffic Games”. Journal of Transport Economics and Policy, 37(1): 47-68.
Qureshi AG, Taniguchi E, Yamada T. (2009E) “An exact solution approach for vehicle routing and scheduling problems with soft time windows”. Transportation Research;45(9), 60–77.
Sarmiento C. and Wilson W. W. (2005) “Spatial Modeling in Technology Adoption Decisions: The Case of Shuttle Train Elevators”. American Agricultural Economics Association, 87 (4): 1034-1045.
Schneider, Michael., (2016). "The vehicle-routing problem with time windows and driver-specific times." European Journal of Operational Research 250.1: 101-119.
Solomon, M. M. (1986). “On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints”. Networks, 16(2), 161-174.
Solomon MM. (1987) “Algorithms for the vehicle routing and scheduling problem with time windows constraints”. Operations Research; 35:254– 65.
Solomon MM, Desrosiers J. (1988) “Time window constrained routing and scheduling problems”. Transportation Science; 22(1):1–13.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J. Y. (1997). “A tabu search heuristic for the vehicle routing problem with soft time windows”.Transportation science, 31(2), 170-186.
Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M., Salamatbakhsh, A., & Norouzi, N. (2011). “A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing”. Journal of manufacturing systems, 30(2), 83-92.
Tavakkoli-Moghaddam, R., Safaei, N., & Shariat, M. “A. (2005). A multi-criteria vehicle routing problem with soft time windows by simulated annealing”. Journal of Industrial Engineering-Int, 1(1), 28-36.
Tembine, H., Altman, E., El-Azouzi, R., & Hayel, Y. (2011). “Bio-inspired delayed evolutionary game dynamics with networking applications”. Telecommunication Systems, 47(1-2), 137-152.
Wang, Z., Li, Y., & Hu, X. (2015). “A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint”. Computers & Industrial Engineering, 89, 162-176.
William H. Sandholm, Emin Dokumacı, and Ratul Lahkar(2006) “The Projection Dynamic, the Replicator Dynamic, and the Geometry of Population Games”. Conference on Optimization for helpful comments.
Xin Miao, Bo Yu, Bao Xi & Yan hong Tang (2010) “Modeling of bilevel games and incentives for sustainable critical infrastructure system”. Ukio Technologinis ir Ekonominis Vystymas, 16(3): 365-379.
Yunrui, G., & Rui, D. (2013). “Evolutionary game of motorized and non-motorized transport in city”. Journal of Henan Institute of Science and Technology (Natural Sciences Edition), 3, 026.
Journal of Industrial and Systems Engineering
Volume 10, Issue 2
April 2017
Pages 35-52

Files

History

  • Receive Date: 21 September 2016
  • Revise Date: 13 January 2017
  • Accept Date: 13 January 2017

Share

How to cite

Statistics