×

zbMATH — the first resource for mathematics

The bi-objective stochastic covering tour problem. (English) Zbl 1251.90361
Summary: We formulate a bi-objective covering tour model with stochastic demand where the two objectives are given by (i) cost (opening cost for distribution centers plus routing cost for a fleet of vehicles) and (ii) expected uncovered demand. In the model, it is assumed that depending on the distance, a certain percentage of clients go from their homes to the nearest distribution center. An application in humanitarian logistics is envisaged. For the computational solution of the resulting bi-objective two-stage stochastic program with recourse, a branch-and-cut technique, applied to a sample-average version of the problem obtained from a fixed random sample of demand vectors, is used within an epsilon-constraint algorithm. Computational results on real-world data for rural communities in Senegal show the viability of the approach.

MSC:
90C29 Multi-objective and goal programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C15 Stochastic programming
Software:
ParadisEO-MOEO; VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Birge, J.R.; Louveaux, F., Introduction to stochastic programming, (1997), Springer New York · Zbl 0892.90142
[2] Current, J.R.; Schilling, D.A., The Median tour and maximal covering tour problems: formulations and heuristics, European journal of operational research, 73, 114-126, (1994) · Zbl 0806.90036
[3] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6, 182-197, (2002)
[4] Drezner, T.; Eiselt, H.A., Consumers in competitive location models, () · Zbl 1133.90362
[5] Doerner, K.; Focke, A.; Gutjahr, W.J., Multicriteria tour planning for mobile healthcare facilities in a developing country, European journal of operational research, 179, 1078-1096, (2006) · Zbl 1163.90599
[6] Gendreau, M.; Laporte, G.; Semet, F., The covering tour problem, Operations research, 45, 568-576, (1997) · Zbl 0887.90122
[7] Gutjahr, W.J., A provably convergent heuristic for stochastic bicriteria integer programming, Journal of heuristics, 15, 227-258, (2009) · Zbl 1172.90477
[8] Kovac, G., Humanitarian logistics in disaster relief operations, International journal of physical distribution and logistics management, 37, 99-114, (2007)
[9] Hachicha, M.; Hodgson, M.J.; Laporte, G.; Semet, F., Heuristics for the multi-vehicle covering tour problem, Computers and operations research, 27, 29-42, (2000) · Zbl 0973.90019
[10] Hodgson, M.J.; Laporte, G.; Semet, F., A covering tour model for planning mobile health care facilities in suhum district, ghana, Journal of regional science, 38, 621-639, (1998)
[11] Jozefowiez, N.; Semet, F.; Talbi, E., The bi-objective covering tour problem, Computers and operations research, 34, 1929-1942, (2007) · Zbl 1190.90044
[12] Laumanns, M.; Thiele, L.; Zitzler, E., An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European journal of operational research, 169, 932-942, (2006) · Zbl 1079.90122
[13] Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., Combinatorial optimization of stochastic multi-objective problems an application to the flow-shop scheduling problem, (), 457-471
[14] Naddef D, Rinaldi G. Branch-and-cut algorithms for the capacitated VRP. In: Toth P, Vigo D, editors. The vehicle routing problem. SIAM monographs on discrete mathematics and applications, Philadelphia; 2002. p. 53-84. · Zbl 1076.90550
[15] Nolz, P.C.; Doerner, K.F.; Gutjahr, W.J.; Hartl, R.F., A biobjective metaheuristic for disaster relief operation planning, (), 157-177
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.