Model and Solution Approach for Multi objective-multi commodity Capacitated Arc Routing Problem with Fuzzy Demand

Document Type : Research Paper


1 Department of Engineering, University of Kurdistan, Sanandaj, Iran

2 University of Kurdistan, Sanandaj, Iran


The capacitated arc routing problem (CARP) is one of the most important routing problems with many applications in real world situations. In some real applications such as urban waste collection and etc., decision makers have to consider more than one objective and investigate the problem under uncertain situations where required edges have demand for more than one type of commodity. So, in this research, a new fuzzy chance constrained programming model based on credibility measure for CARP with two objectives: minimizing the number of vehicle and minimizing the total travel cost is formulated. In this model each required edge has demand for more than one type of commodity and also all demands for each commodity are supposed to be triangular fuzzy numbers. Then we develop a multi-objective genetic algorithm using the Pareto ranking technique and hybrid it with stochastic simulation to design an intelligent algorithm to solve the fuzzy chance constrained model. In order to improve the quality of final solutions, we also propose a new heuristic method to generate a good initial solution in initial population of genetic algorithm. Some data sets with fuzzy demand generated randomly are used to evaluate and investigate key characteristics of the new proposed model and solution approach.


Main Subjects

[1] Beullens P., Muyldermans L., CattrysseD.,VanOudheusden D. (2003), A guided local search heuristic
for the capacitated arc routing problem; European Journal of Operational Research 147(3); 629–643.
[2] Christiansen C.H., Lysgaard J., Wøhlk S. (2009), A Branch-and-Price Algorithm for the Capacitated
Arc Routing Problem with Stochastic Demands; Operations Research Letters 37; 392-398.
[3] Coello C.A.C. (1999), A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization
Techniques; Knowledge and Information Systems 1(3); 269–308.
[4] DeArmon J.S. (1981),A comparison of heuristics for the capacitated chinese postman problem;
Dissertation, University of Maryland.
[5] Deb K., Pratap A., Agarwal S., Meyarivan T. (2002), A fast and elitist multiobjective genetic
algorithm: NSGA-II; IEEE Transactions on Evolutionary Computation 6(2); 182–197.
[6] Dijkgraaf E., Gradus R. (2007), Fair competition in the refuse collection market; Applied Economic
Letters 14(10); 701–704.
[7] Dijkstra E.W. (1959), A note on two problems in connection with graphs; NumerischeMathematik
1(1); 269–271.
[8] Dror M., Stern H.I. (1979), Routing Electric Meter Readers; Computers and Operations Research
6(4); 209–223.
[9] Dror M., Levy L. (1986), A vehicle routing improvement algorithm comparison of a greedy and a
matching implementation for inventory routing; Computer and Operation Research 13(1); 33–45.
[10] Eglese R.W., Li L. (1992), Efficient Routing for Winter Gritting; Journal of Operational Research
Society 43(11); 1031–1034.
[11] Fleury G., Lacomme,P., Prins C. (2004), Evolutionary algorithms for stochastic arc routing
problems,.In: Raidl G.R., Rothlauf F., Smith G.D., Squillero G., Cagnoni S., Branke J., Corne D.W.,
Drechsler R., Jin Y., Johnson C.G. (Eds.), Applications of Evolutionary Computing, Springer-Verlag:
Berlin; 501-512.
[12] Fleury G., Lacomme P., Prins C., Sevaux M. (2005), A memetic algorithm for a bi-objective and
stochastic CARP; Multi Objective Combinatorial Optimization, The 6th Metaheuristics International
Conference; 22-26.
[13] Garcia-Najera A., Bullinaria J.A. (2009), Bi-objective optimization for the vehicle routing problem
with time windows: using route similarity to enhance performance, In: Ehrgott M., Fonseca C.,
Gandibleux X., Hao J.K., Sevaux M., editors; Proceedings of fifth international conference on
evolutionary multi- criterion optimization, Lecture Notes in Computer Science 5467; 275–89.
[14] Garcia-Najera A.,Bullinaria J.A. (2011), An improved multi-objective evolutionary algorithm for the
vehicle routing problem with time windows; Computers and Operation Research 38(1); 287-300.
[15] Gen M., Cheng R.W. (2000), Genetic algorithms and engineering optimization; John wiley&Sons;
[16] Goldberg D.E. (1989), Genetic Algorithms in Search, Optimization and Machine Learning; Addison
[17] Goldberg D.E., Deb K. (1991), A comparative analysis of selection schemes used in genetic
algorithms; In: Foundations of genetic algorithms, Morgan Kaufmann publisher; 69–93.
[18] Golden B.L., Wong R.T. (1981), Capacitated arc routing problems; Networks 11; 305–315.
[19] Golden B.L., DeArmon J.S., Baker E.K. (1983), Computational experiments with algorithms for a
class of routing problems; Computers and Operations Research 10; 47–59.
[20] Grandinetti1 L., Guerriero F., Lagana D., Pisacane O. (2010), An approximate e-constraint method for
the Multi-objective Undirected Capacitated Arc Routing Problem; Lecture Notes in Computer
Science6049; 214-255.
[21] Greistorfer P. (2003), A Tabu Scatter Search Metaheuristic for the Arc Routing Problem; Computers
and Industrial Engineering 44(2); 249–266.
[22] Han H.S., Yu J.J., Park C.G., Lee J. G. (2004), Development of inspection gauge system for gas
pipeline; Korean Society Mechanical Engineering International Journal 18(3); 370–378.
[23] Hertz A., Laporte G., Mittaz M. (2000), Atabu search heuristic for the capacitated arc routing problem;
Operations Research 48(1); 129–135.
[24] Hertz A., Mittaz M. (2001), A variable neighborhood descent algorithm for the undirected capacitated
arc routing problem; Transportation Science 35(4); 425–434.
[25] Kaufmann A., Gupta M.M. (1985), Introduction to Fuzzy Arithmetic, Theory and Applications; Van
Nostrand Reinhold, New York.
[26] Labelle A., Langevin A., Campbell J.F. (2002), Sector design for snow removal and disposal in urban
areas; Socio-Economic Planning Sciences 36(3); 183–202.
[27] Lacomme P., Prins C., Ramdane-CherifW. (2004), Competitive memetic algorithms for arc routing
problems; Annals of Operation Research 131; 159–185.
[28] Lacomme P., Prins C., Sevaux M. (2006), A genetic algorithm for a biobjective capacitated arc routing
problem; Computers and Operations Research 33(12); 3473–3493.
[29] Liu B. (2006), A survey of credibility theory; Fuzzy Optimization and Decision Making 5(4); 387-408.
[30] Mei Y., Tang K., Yao X. (2010), Capacitated arc routing problem in uncertain environments; IEEE
world congress on Computational Intelligence; Spain, 1400-1407.
[31] Mei Y., Tang K., Yao X. (2011), Decomposition-Based Memetic Algorithm for Multi-Objective
Capacitated Arc Routing Problem; IEEE Transactions on Evolutionary Computation15(2);151-16.
[32] Mitra K. (2009), Multiobjective optimization of an industrial grinding operation under uncertainty;
Chemical Engineering Science 64; 5043-5056.
[33] Muyldermans L., Pang G. (2010), A guided local search procedure for the multi-compartment
capacitated arc routing problem, Computers and Operations Research 37; 1662–1673.
[34] Potvin J.Y., Bengio S. (1996), The vehicle routing problem with time windows, part II: Genetic
search;Informs Journal of Computing 8(2); 165–172.
[35] Santos L., Coutinho-Rodrigues J.R., Current J.R. (2009), An improved heuristic for the capacitated arc
routing problem; Computers and OperationsResearch 36(9); 2632–2637.
[36] Tang K., Mei Y., Yao X. (2009), Memetic Algorithm with Extended Neighborhood Search for
Capacitated Arc Routing Problems; IEEE Transactions on Evolutionary Computation 13(5); 1151-
[37] Tobin G.A., Brinkmann R. (2002), The effectiveness of street sweepers in removing pollutants from
road surfaces in Florida; Journal of Environmental Science and Health (Part A) 37(9); 1687–1700.
[38] Ulusoy G. (1985), The fleet size and mix problem for capacitated arc routing; European Journal of
Operational Research 22; 329–37.
[39] Van Veldhuizen D.A. (1999), Multiobjective Evolutionary Algorithms: Classifications, Analyses, and
New Innovations; Ph.D. thesis, AFIT/DS/ENG/99-01, Air Force Institute of Technology, Wright-
Patterson AFB, Ohio.
[40] Van Veldhuizen D.A., Lamont G.B. (2000), Multiobjective evolutionary algorithms: Analyzing the
state-of-the-art; Evolutionary Computation 8(2); 125-147.
[41] Wøhlk S. (2005), Contributins to arc routing; PhD thesis, University of Southern Denmark.
[42] Zadeh L.A. (1965), Fuzzy Sets; Information and Control 8; 338-353.
[43] Zadeh L.A. (1978), Fuzzy sets as a basis for a theory of possibility; Fuzzy sets and Systems 1; 3-28.