An Attribute Based Similarity Function for VRP Decision Support
DOI:
https://doi.org/10.7494/dmms.2012.6.2.65Keywords:
Solution Variety, Solution Similarity, Vehicle Routing Problem (VRP), DSSAbstract
When solving problems in the real world using optimization tools, the model solved by the tools is often only an approximation of the underlying, real, problem. In these circumstances, a decision maker (DM) should consider a diverse set of good solutions, not just an optimal solution as produced using the model. On the other hand, the same DM will only be interested in seeing a few of the alternative solutions, and not the plethora of solutions often produced by modern search techniques. There is thus a need to distinguish between good solutions using the attributes of solutions. We develop a distance function of the type proposed in the Psychology literature by Tversky (1977) for the class of VRP problems. We base our difference on the underlying structure of solutions. A DM is often interested in focusing on a set of solutions fulfilling certain conditions that are of specific importance that day, or in general, like avoiding a certain road due to construction that day. This distance measure can also be used to generate solutions containing these specific classes of attributes, as the normal search process might not supply enough of these interesting solutions. We illustrate the use of the functions in a Multi-objective Decision Support System (DSS) setting, where the DM might want to see the presence (or absence) of certain attributes, and show the importance of identifying solutions not on the Pareto front. Our distance measure can use any attributes of the solutions, not just those defined in the optimization model.
References
Bontoux B. & Feillet D. (2008). Ant colony optimization for the traveling purchaser problem. Computers & Operations Research, 35(2), pp. 628–637. DOI: http://doi.org/10.1016/j.cor.2006.03.023.
Caprara A. (1999). Sorting permutations by reversals and Eulerian cycle decompositions. SIAM Journal on Discrete Mathematics, 12(1), pp. 91–110. DOI: http://doi.org/10.1137/S089548019731994X.
Cordeau J.-F., Laporte G. & Mercier A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), pp. 928–936. DOI: http://doi.org/10.1057/palgrave.jors.2601163.
Corne D.W., Knowles J.D. & Oates M.J. (2000). The Pareto envelope-based selection algorithm for multiobjective optimization. In: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo & H.-P. Schwefel (Eds.). Parallel Problem Solving from Nature – PPSN VI. Lecture Notes in Computer Science, vol. 1917, Springer, Berlin–Heidelberg, pp. 839–848. DOI: http://doi.org/10.1007/3-540-45356-3_82.
Danna E. & Woodruff D.L. (2009). How to select a small set of diverse solutions to mixed integer programming problems: Good news and bad news. Operations Research Letters, 37(4), pp. 255–260. DOI: http://doi.org/10.1016/j.orl.2009.03.004.
Dimmock N. & Maddison I. (2004). Peer-to-peer collaborative spam detection. ACM Crossroads, 11(2), art. no. 4. DOI: http://doi.org/10.1145/1144403.1144407.
Glover F. & Laguna M. (1997). Tabu Search. Kluwer Academic Publishers, Boston. DOI: http://doi.org/10.1007/978-1-4615-6089-0.
Goertzel B. (1997). From Complexity to Creativity: Explorations in Evolutionary, Autopoietic, and Cognitive Dynamics. Plenum Press, New York. DOI: http://doi.org/10.1007/b102389.
Hamming R.W. (1950). Error detecting and error correcting codes. Bell System Technical Journal, 29(2), pp. 147–160. DOI: http://doi.org/10.1002/j.1538-7305.1950.tb00463.x.
Hartl R.F., Hasle G. & Janssens G.K. (2006). Special issue on rich vehicle routing problems. Central European Journal of Operations Research, 14(2), pp. 103–104. DOI: http://doi.org/10.1007/s10100-006-0162-9.
Jozefowiez N., Semet F. & Talbi E.-G. (2008). Multi-objective vehicle routing problems. European Journal of Operational Research, 189(2), pp. 293–309. DOI: http://doi.org/10.1016/j.ejor.2007.05.055.
Laguna M. & Martí R. (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, Boston. DOI: http://doi.org/10.1007/978-1-4615-0337-8.
Løkketangen A. & Woodruff D.L. (2005). A distance function to support optimized selection decisions. Decision Support Systems, 39(3), pp. 345–354. DOI: http://doi.org/10.1016/j.dss.2004.01.001.
Medin D.L., Goldstone R.L. & Gentner D. (1993). Respects for similarity. Psychological Review, 100(2), pp. 254–278. DOI: http://doi.org/10.1037/0033-295X.100.2.254.
Oppen J. & Løkketangen A. (2006). Arc routing in a node routing environment. Computers & Operations Research, 33(4), pp. 1033–1055. DOI: http://doi.org/10.1016/j.cor.2004.09.004.
Oppen J., Løkketangen A. & Desrosiers J. (2010). Solving a rich vehicle routing and inventory problem using column generation. Computers & Operations Research, 37(7), pp. 1308–1317. DOI: http://doi.org/10.1016/j.cor.2009.09.014.
Reeves C.R. (2003). Genetic algorithms. In: F. Glover & G.A. Kochenberger (Eds.). Handbook of Metaheuristics. Kluwer Academic Publishers, Boston, pp. 55–82. DOI: http://doi.org/10.1007/0-306-48056-5_3.
Ronald S. (1998). More distance functions for order-based encodings. In: 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence, pp. 558–563. DOI: http://doi.org/10.1109/ICEC.1998.700089.
Ryu T.-W. & Eick C.F. (1998). A unified similarity measure for attributes with set or bag of values for database clustering. In: Proceedings of the 6th International Workshop on Rough Sets, Data Mining and Granular Computing (RSDMGrC’98), Research Triangle Park, North Carolina.
Ryu T.-W. & Eick C.F. (2005). A database clustering methodology and tool. Information Sciences, 171(1–3), pp. 29–59. DOI: http://doi.org/10.1016/j.ins.2004.03.016.
Sevaux M. & Sörensen K. (2005). Permutation distance measures for memetic algorithms with population management. In: Proceedings of the 6th Metaheuristics International Conference (MIC 2005), Vienna, pp. 832–838.
Sörensen K. (2006). Route stability in vehicle routing decisions: A bi-objective approach using metaheuristics. Central European Journal of Operations Research, 14(2), pp. 193–207. DOI: http://doi.org/10.1007/s10100-006-0168-3.
Sörensen K. (2007). Distance measures based on the edit distance for permutation-type representations. Journal of Heuristics, 13(1), pp. 35–47. DOI: http://doi.org/10.1007/s10732-006-9001-3.
Sörensen K. & Sevaux M. (2006). MA–PM: Memetic algorithms with population management. Computers & Operations Research, 33(5), pp. 1214–1225. DOI: http://doi.org/10.1016/j.cor.2004.09.011.
Toth P. & Vigo D. (Eds.). (2002). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia. DOI: http://doi.org/10.1137/1.9780898718515.
Tversky A. (1977). Features of similarity. Psychological Review, 84(4), pp. 327–352. DOI: http://doi.org/10.1037/0033-295X.84.4.327.
Wagner R.A. & Fischer M.J. (1974). The string-to-string correction problem. Journal of the ACM, 21(1), pp. 168–173. DOI: http://doi.org/10.1145/321796.321811.
