Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm. (English) Zbl 1349.90098
Summary: This study considers a multi-objective dynamic stochastic districting and routing problem in which the customers of a territory stochastically evolve over several periods of a planning horizon, and where the number of service vehicles, the compactness of the districts, the dissimilarity measure of the districts and an equity measure of vehicles profit are considered as objectives. The problem is modeled and solved as a two-stage stochastic program, where in each period, districting decisions are made in the first stage, and the Beardwood-Halton-Hammersley formula is used to approximate the expected routing cost of each district in the second stage. An enhanced multi-objective evolutionary algorithm (MOEA), i.e., the preference-inspired co-evolutionary algorithm using mating restriction, is developed for the problem. The algorithm is tested on randomly generated instances and is compared with two state-of-the-art MOEAs. Computational results confirm the superiority and effectiveness of the proposed algorithm. Moreover, a procedure for selecting a preferred design for the proposed problem is described.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B10 | Deterministic network models in operations research |
| 90C15 | Stochastic programming |
| 90C29 | Multi-objective and goal programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
districting; routing; co-evolutionary algorithm; multi-objective optimization; mating restrictionReferences:
| [1] | Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W. J., The travelling salesman problem: a computational study (2006), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 1130.90036 |
| [2] | Bader, J.; Zitzler, E., HypE: an algorithm for fast hypervolume-based many-objective optimization, Evol Comput, 19, 1, 45-76 (2011) |
| [3] | Beardwood, J.; Halton, J. H.; Hammersley, J. M., The shortest path through many points, Math Proc Camb Philos Soc, 55, 4, 299-327 (1959) · Zbl 0118.35601 |
| [4] | Blais, M.; Lapierre, S. D.; Laporte, G., Solving a home care districting problem in an urban setting, J Oper Res Soc, 54, 11, 1141-1147 (2003) · Zbl 1095.90512 |
| [5] | Bozkaya, B.; Erkut, E.; Laporte, G., A tabu search heuristic and adaptive memory procedure for political districting, Eur J Oper Res, 144, 1, 12-26 (2003) · Zbl 1037.90535 |
| [6] | Bozkaya, B.; Erkut, E.; Haight, D.; Laporte, G., Designing new electoral districts for the city of Edmonton, Interfaces, 41, 6, 534-C547 (2011) |
| [7] | Butsch, A.; Kalcsics, J.; Laporte, G., Districting for arc routing, INFORMS J Comput, 26, 4, 809-C824 (2014) · Zbl 1304.90218 |
| [8] | Carlsson, J. G.; Devulapalli, R., Dividing a territory among several facilities, INFORMS J Comput, 25, 4, 730-742 (2013) |
| [9] | Carlsson, J. G., Dividing a territory among several vehicles, INFORMS J Comput, 24, 4, 565-577 (2012) · Zbl 1460.90028 |
| [10] | Carlsson, J. G.; Delage, E., Robust partitioning for stochastic multivehicle routing, Oper Res, 61, 3, 727-744 (2013) · Zbl 1273.90022 |
| [11] | Coello, C.; Lamont, G.; van Veldhuizen, D., Evolutionary algorithms for solving multi-objective problems (2007), Springer: Springer New York · Zbl 1142.90029 |
| [12] | D׳Amico, S. J.; Wang, S. J.; Batta, R.; Rump, C. M., A simulated annealing approach to police district design, Comput Oper Res, 29, 6, 667-684 (2002) · Zbl 0995.90609 |
| [13] | Deb, K., Multi-objective optimization using evolutionary algorithms (2001), John Wiley and Sons, Ltd: John Wiley and Sons, Ltd Chichester, U.K. · Zbl 0970.90091 |
| [14] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans Evol Comput, 6, 2, 182-197 (2002) |
| [15] | Deb, K.; Mohan, M.; Mishra, S., Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evol Comput, 13, 4, 501-525 (2005) |
| [16] | Drexl, A.; Haase, K., Fast approximation methods for sales force deployment, Manag Sci, 45, 10, 1307-1323 (1999) · Zbl 1231.90250 |
| [17] | Ferland, J. A.; Guénette, G., Decision support system for the school districting problem, Oper Res, 38, 1, 15-21 (1990) |
| [21] | Fonseca, C.; Fleming, P., Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulation, IEEE Trans Syst Man Cybern Part A: Syst Hum, 28, 1, 26-37 (1998) |
| [23] | Gendreau, M.; Laporte, G.; Séguin, R., A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Oper Res, 44, 3, 469-477 (1996) · Zbl 0864.90043 |
| [24] | Groër, C.; Golden, B. L.; Wasil, E. A., The consistent vehicle routing problem, Manuf Serv Oper Manag, 11, 4, 630-643 (2009) |
| [25] | Haugland, D.; Ho, S. C.; Laporte, G., Designing delivery districts for the vehicle routing problem with stochastic demands, Eur J Oper Res, 180, 3, 997-1010 (2007) · Zbl 1121.90021 |
| [29] | Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited, Oper Res, 36, 6, 929-936 (1988) · Zbl 0665.90096 |
| [30] | Kalcsics, J.; Nickel, S.; Schröder, M., Towards a unified territorial design approach - Applications, Algorithms and GIS integration TOP, 13, 1, 1-56 (2005) · Zbl 1072.90058 |
| [31] | King, D. M.; Jacobson, S. H.; Sewell, E. C.; Tam Cho, W. K., Geo-Graphs: an efficient model for enforcing contiguity and hole constraints in planar graph partitioning, Oper Res, 60, 5, 1213-1228 (2012) · Zbl 1262.90184 |
| [32] | Laporte, G.; Louveaux, F. V.; Mercure, H., A priori optimization of the probabilistic traveling salesman problem, Oper Res, 42, 3, 543-549 (1994) · Zbl 0810.90124 |
| [33] | Lei, H.; Laporte, G.; Guo, B., The capacitated vehicle routing problem with stochastic demands and time windows, Comput Oper Res, 38, 12, 1775-1783 (2011) · Zbl 1215.90013 |
| [34] | Lei, H.; Laporte, G.; Guo, B., Districting for routing with stochastic customers, EURO J Transp Logist, 1, 1, 67-85 (2012) |
| [35] | Lei, H.; Laporte, G.; Liu, Y.; Zhang, T., Dynamic design of sales territories, Comput Oper Res, 56, 84-92 (2015) · Zbl 1348.90106 |
| [37] | López-Pérez, J. F.; Ríos-Mercado, R. Z., Embotelladoras ARCA uses operations research to improve territory design plans, Interfaces, 43, 3, 209-220 (2013) |
| [38] | Mehrotra, A.; Johnson, E. L.; Nemhauser, G. L., An optimization based heuristic for political districting, Manag Sci, 44, 8, 1100-1114 (1992) · Zbl 0988.90542 |
| [39] | Miettinen, K., Nonlinear multiobjective optim, vol. 12 (1999), Springer: Springer Heidelberg · Zbl 0949.90082 |
| [40] | Novaes, A. G.N.; Souza de Cursi, J. E.; da Silva, A. C.L.; Souza, J. C., Solving continuous location-districting problems with Voronoi diagrams, Comput Oper Res, 36, 1, 40-59 (2009) · Zbl 1163.90621 |
| [42] | Purshouse, R.; Fleming, P., On the evolutionary optimization of many conflicting objectives, IEEE Trans Evol Comput, 11, 6, 770-784 (2007) |
| [44] | Ricca, F.; Simeone, B., Local search algorithms for political districting, Eur J Oper Res, 189, 3, 1409-1426 (2008) · Zbl 1146.91016 |
| [45] | Ríos-Mercado, R. Z.; Fernández, E., A reactive GRASP for a commercial territory design problem with multiple balancing requirements, Comput Oper Res, 36, 3, 755-776 (2009) · Zbl 1157.90515 |
| [46] | Salazar-Aguilar, M. A.; Ríos-Mercado, R. Z.; González-Velarde, J. L., A bi-objective programming model for designing compact and balanced territories in commercial districting, Transp Res Part C, 19, 5, 885-895 (2011) |
| [47] | Salazar-Aguilar, M. A.; Ríos-Mercado, R. Z.; González-Velarde, J. L.; Molina, J., Multiobjective scatter search for a commercial territory design problem, Ann Oper Res, 199, 1, 343-360 (2012) · Zbl 1269.90096 |
| [48] | Salazar-Aguilar, M. A.; Ríos-Mercado, R. Z.; González-Velarde, J. L., GRASP strategies for a bi-objective commercial territory design problem, J Heuristics, 19, 2, 179-200 (2013) |
| [49] | Scott, M. N.; Cromley, R. G.; Cromley, E. K., Multi-objective analysis of school district regionalization alternatives in Connecticut, Prof Geogr, 48, 1, 1-14 (1996) |
| [50] | Skiera, B.; Albers, S., COSTA: contribution optimizing sales territory alignment, Market Sci, 17, 3, 196-213 (1998) |
| [51] | Tavares-Pereira, F.; Figueira, J. R.; Mousseau., V.; Bernard, R., Multiple criteria districting problems, Ann Oper Res, 154, 1, 69-92 (2007) · Zbl 1157.90463 |
| [53] | Wang, R.; Purshouse, R. C.; Fleming, P. J., Preference-inspired co-evolutionary algorithms for many-objective optimisation, IEEE Trans Evol Comput, 17, 4, 474-494 (2013) |
| [56] | Wang, R.; Purshouse, R. C.; Fleming, P. J., General framework for localised multi-objective evolutionary algorithms, Inf Sci, 258, 2, 29-53 (2014) |
| [57] | Wang, R.; Purshouse, R. C.; Fleming, P. J., Preference-inspired co-evolutionary algorithms using weight vectors, Eur J Oper Res, 243, 2, 423-441 (2015) · Zbl 1346.90755 |
| [58] | Wang, R.; Purshouse, R. C.; Giagkiozis, I.; Fleming, P. J., The iPICEA-g: a new hybrid evolutionary multi-criteria decision making approach using the brushing technique, Eur J Oper Res, 243, 2, 442-453 (2015) · Zbl 1346.91060 |
| [59] | Wei, B. C.; Chai, W. Y., A multiobjective hybrid metaheuristic approach for GIS-based spatial zone model, J Math Model Algorithms, 3, 3, 245-261 (2004) · Zbl 1146.90539 |
| [60] | Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans Evol Comput, 11, 6, 712-731 (2007) |
| [61] | Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evol Comput, 1, 1, 179-200 (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
