Optimization Using Simulation of the Vehicle Routing Problem
A key element of many distribution systems is the
routing and scheduling of vehicles servicing a set of customers. A
wide variety of exact and approximate algorithms have been
proposed for solving the vehicle routing problems (VRP). Exact
algorithms can only solve relatively small problems of VRP, which is
classified as NP-Hard. Several approximate algorithms have proven
successful in finding a feasible solution not necessarily optimum.
Although different parts of the problem are stochastic in nature; yet,
limited work relevant to the application of discrete event system
simulation has addressed the problem. Presented here is optimization
using simulation of VRP; where, a simplified problem has been
developed in the ExtendSimTM simulation environment; where,
ExtendSimTM evolutionary optimizer is used to minimize the total
transportation cost of the problem. Results obtained from the model
are very satisfactory. Further complexities of the problem are
proposed for consideration in the future.
[1] R. Baldacci, P. Toth, and D. Vigo, "Exact algorithms for routing
problems under vehicle capacity constraints," Ann Oper Res, vol. 175,
pp. 213-245, 2010.
[2] N. Azi, M. Gendreau, and J.-Y. Potvin, "An exact algorithm for a singlevehicle
routing problem with time windows and multiple routes,"
European Journal of operational Research, vol. 178, pp. 755-766, 2007.
[3] R. Baldacci, E. Hadjiconstantinou, and A. Mingozzi, "An Exact
Algorithm for the Capacitated Vehicle Routing Problem Based on a
Two-Commodity NetworkFlow Formulation," Operations Research,
vol. 52, pp. 723-738, 2004.
[4] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time
Windows, Part I: Route Construction and Local Search Algorithms,"
Transportation science, vol. 39, pp. 104-118, 2005.
[5] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time
Windows, Part II: Metaheuristics," Transportation science, vol. 39, pp.
119-139, 2005.
[6] U. Derigs and K. Reuter, "A simple and efficient tabu search heuristic
for solving the open vehicle routing problem," Journal of the
Operational Research Society, vol. 60, pp. 1658-1669, 2009.
[7] M. Desrochers, J. K. Lenstra, and M. W. P. Savelsbergh, "A
classification scheme for and scheduling problems vehicle routing,"
European Journal of operational Research, vol. 46, pp. 322-332, 1990.
[8] R. H. Ballou, Business Logistics/ Supply Chain Management, 5th ed.
Pearson, 2004.
[9] S. Ropke, "Heuristics and exact algorithms for vehicle routing
problems," Ph.D., Department of Computer Science University of
Copenhagen, 2005.
[10] Z. Fu, R. Eglese, and L. Li, "A unified tabu search algorithm for vehicle
routing problems with soft time windows," Journal of the Operational
Research Society, vol. 59, pp. 663 --673, 2008.
[11] M. M. Solomon and J. Desrosiers, "Time window constrained routing
and scheduling Problems," Transportation science, vol. 22, 1988.
[12] W. Maden, R. Eglese, and D. Black, "Vehicle routing and scheduling
with time-varying data: A case study," Journal of the Operational
Research Society, vol. 61, pp. 515-522, 2010.
[13] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research,
8th ed.: McGraw-Hill, 2005.
[14] P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia: SIAM,
2002.
[15] A. M. Campbell and M. Savelsbergh, "Efficient Insertion Heuristics for
Vehicle Routing and Scheduling Problems," Transportation science, vol.
38, pp. 369-378, 2004.
[16] G. Laporte, "The Vehicle Routing Problem: An overview of exact and
approximate algorithms," European Journal of operational Research,
vol. 59, pp. 345-358, 1992.
[17] M. M. Solomon, "Algorithms for the Vehicle Routing and Scheduling
Problems with Time Window Constraints," Operations Research, vol.
35, pp. 254-265, 1987.
[18] N. Wassan, "A reactive tabu search for the vehicle routing problem,"
Journal of the Operational Research Society, vol. 57, pp. 111-116,
2006.
[19] B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle
routing problem," Computers & Operations Research, vol. 30, pp. 787-
800, 2003.
[20] S. Zhongyue and G. Zhongliang, "Vehicle Routing Problem Based on
Object-oriented Discrete Event Simulation," presented at the
International Conference on Advanced Computer Control ICACC, 2010.
[21] J. Faulin, M. Gilibert, A. A. Juan, X. Vilajosana, and R. Ruiz, "SR-1: A
Simulation-based Heuristic Algorithm for the Capacitated Vehicle
Routing Problem," presented at the The 2008 Winter Simulation
Conference, 2008.
[22] D. Feillet, P. Dejax, and M. Gendreau, "Traveling Salesman Problems
with Profits," Transportation science, vol. 39, pp. 188-205, 2005.
[23] R. V. Kulkarni and P. R. Bhave, "Integer programming formulations of
vehicle routing problems," European Journal of operational Research,
vol. 20, pp. 58-67, 1985.
[24] "ExtendSim 8 User Guide," Imagine That Inc.2007.
[1] R. Baldacci, P. Toth, and D. Vigo, "Exact algorithms for routing
problems under vehicle capacity constraints," Ann Oper Res, vol. 175,
pp. 213-245, 2010.
[2] N. Azi, M. Gendreau, and J.-Y. Potvin, "An exact algorithm for a singlevehicle
routing problem with time windows and multiple routes,"
European Journal of operational Research, vol. 178, pp. 755-766, 2007.
[3] R. Baldacci, E. Hadjiconstantinou, and A. Mingozzi, "An Exact
Algorithm for the Capacitated Vehicle Routing Problem Based on a
Two-Commodity NetworkFlow Formulation," Operations Research,
vol. 52, pp. 723-738, 2004.
[4] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time
Windows, Part I: Route Construction and Local Search Algorithms,"
Transportation science, vol. 39, pp. 104-118, 2005.
[5] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time
Windows, Part II: Metaheuristics," Transportation science, vol. 39, pp.
119-139, 2005.
[6] U. Derigs and K. Reuter, "A simple and efficient tabu search heuristic
for solving the open vehicle routing problem," Journal of the
Operational Research Society, vol. 60, pp. 1658-1669, 2009.
[7] M. Desrochers, J. K. Lenstra, and M. W. P. Savelsbergh, "A
classification scheme for and scheduling problems vehicle routing,"
European Journal of operational Research, vol. 46, pp. 322-332, 1990.
[8] R. H. Ballou, Business Logistics/ Supply Chain Management, 5th ed.
Pearson, 2004.
[9] S. Ropke, "Heuristics and exact algorithms for vehicle routing
problems," Ph.D., Department of Computer Science University of
Copenhagen, 2005.
[10] Z. Fu, R. Eglese, and L. Li, "A unified tabu search algorithm for vehicle
routing problems with soft time windows," Journal of the Operational
Research Society, vol. 59, pp. 663 --673, 2008.
[11] M. M. Solomon and J. Desrosiers, "Time window constrained routing
and scheduling Problems," Transportation science, vol. 22, 1988.
[12] W. Maden, R. Eglese, and D. Black, "Vehicle routing and scheduling
with time-varying data: A case study," Journal of the Operational
Research Society, vol. 61, pp. 515-522, 2010.
[13] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research,
8th ed.: McGraw-Hill, 2005.
[14] P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia: SIAM,
2002.
[15] A. M. Campbell and M. Savelsbergh, "Efficient Insertion Heuristics for
Vehicle Routing and Scheduling Problems," Transportation science, vol.
38, pp. 369-378, 2004.
[16] G. Laporte, "The Vehicle Routing Problem: An overview of exact and
approximate algorithms," European Journal of operational Research,
vol. 59, pp. 345-358, 1992.
[17] M. M. Solomon, "Algorithms for the Vehicle Routing and Scheduling
Problems with Time Window Constraints," Operations Research, vol.
35, pp. 254-265, 1987.
[18] N. Wassan, "A reactive tabu search for the vehicle routing problem,"
Journal of the Operational Research Society, vol. 57, pp. 111-116,
2006.
[19] B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle
routing problem," Computers & Operations Research, vol. 30, pp. 787-
800, 2003.
[20] S. Zhongyue and G. Zhongliang, "Vehicle Routing Problem Based on
Object-oriented Discrete Event Simulation," presented at the
International Conference on Advanced Computer Control ICACC, 2010.
[21] J. Faulin, M. Gilibert, A. A. Juan, X. Vilajosana, and R. Ruiz, "SR-1: A
Simulation-based Heuristic Algorithm for the Capacitated Vehicle
Routing Problem," presented at the The 2008 Winter Simulation
Conference, 2008.
[22] D. Feillet, P. Dejax, and M. Gendreau, "Traveling Salesman Problems
with Profits," Transportation science, vol. 39, pp. 188-205, 2005.
[23] R. V. Kulkarni and P. R. Bhave, "Integer programming formulations of
vehicle routing problems," European Journal of operational Research,
vol. 20, pp. 58-67, 1985.
[24] "ExtendSim 8 User Guide," Imagine That Inc.2007.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:64345", author = "Nayera E. El-Gharably and Khaled S. El-Kilany and Aziz E. El-Sayed", title = "Optimization Using Simulation of the Vehicle Routing Problem", abstract = "A key element of many distribution systems is the
routing and scheduling of vehicles servicing a set of customers. A
wide variety of exact and approximate algorithms have been
proposed for solving the vehicle routing problems (VRP). Exact
algorithms can only solve relatively small problems of VRP, which is
classified as NP-Hard. Several approximate algorithms have proven
successful in finding a feasible solution not necessarily optimum.
Although different parts of the problem are stochastic in nature; yet,
limited work relevant to the application of discrete event system
simulation has addressed the problem. Presented here is optimization
using simulation of VRP; where, a simplified problem has been
developed in the ExtendSimTM simulation environment; where,
ExtendSimTM evolutionary optimizer is used to minimize the total
transportation cost of the problem. Results obtained from the model
are very satisfactory. Further complexities of the problem are
proposed for consideration in the future.", keywords = "Discrete event system simulation, optimization using simulation, vehicle routing problem.", volume = "7", number = "6", pages = "1315-7", }
