Models for multi-path covering-routing problems
Tóm tắt
Research on covering has concentrated on problems where the facilities are small inrelation to their cover sets and can justifiably be regarded as points. However, representationby a point is not reasonable for all facilities. In this paper, our objective is to consider pathcovering problems and study them with particular emphasis on multi-path models. We introducea new problem, 2-MPSP, then formulate it and some of its variants. We also outlinetwo solution approaches for solving the 2-MPSP problem.
Tài liệu tham khảo
S. Belardo, J. Harrald, W.A. Wallace and J. Ward, A partial covering approach to siting response resources for major maritime oil spills, Manag. Sci. 30(1981)1184 – 1196.
T.L. Bell and R.L. Church, Location allocation modelling in archaeological settlement pattern research: Some preliminary applications, World Archaeology 16(1985)354– 371.
V.L. Bennett, D. Eaton and R.L. Church, Selecting sites for rural health workers, Social Science and Medicine 16(1982)63 – 72.
T.B. Boffey, Multiobjective routing problems, TOP 3(1995)167 – 220.
T.B. Boffey and J. Karkazis, Location, routing and the environment, in: Facility Location: A Survey of Applications and Methods, ed. Z. Drezner, Springer, New York, 1995, chapter 19.
T.B. Boffey and S.C. Narula, Multiobjective covering and routing problems, in: Essays in Decision Making: A Volume in Honor of Stanley Zionts, eds. M. Karwan, J. Spronk and J. Wallenius, Springer, 1997.
T.B. Boffey, B.A.H. El Lateef and R.C. Williams, A Lagrangean – tabu search approach to a covering/routing problem, Working Paper, MBB97-01, Department of Mathematical Sciences, Liverpool University, 1997.
J.R. Church and C.S. ReVelle, The maximal covering location problem, Papers Regional Science Assoc. 32(1974)101 – 118.
J.L. Cohon, Multiobjective Programming and Planning, Academic Press, New York, 1978.
J.R. Current, C.S. ReVelle and J.L. Cohon, The maximum covering/shortest path problem: A multiobjective network design and routing formulation, Eur. J. Oper. Res. 21(1985)189– 199.
J.R. Current, C.S. ReVelle and J.L. Cohon, The hierarchical network design problem, Eur. J. Oper. Res. 27(1986)57 – 66.
J.R. Current, C.S. ReVelle and J.L. Cohon, The median shortest path problem: A multiobjective approach to analyze cost vs. accessibility in the design of transportation networks, Transp. Sci. 21 (1987)188 – 197.
J.R. Current and D.A. Schilling, The covering salesman problem, Transp. Sci. 23(1989)208 – 213.
J.R. Current and D.A. Schilling, The median tour and maximal covering tour problems, Eur. J. Oper. Res. 73(1994)114 – 126.
Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
F.R. Dwyer and J.R. Evans, A branch and bound algorithm for the list selection problem in direct mail advertising, Manag. Sci. 27(1981)658 – 667.
D.J. Eaton, M.S. Daskin, S.B. Bulloch and G. Jansma, Determining emergencey medical service deployment in Austin, Texas, Interfaces 15(1985)96 – 108.
D. J. Eaton, M. Hector, V. Sanchez, R. Lantigua and J. Morgan, Determining ambulance deployment in Santo Domingo, Dominican Republic, J. Oper. Res. Soc. 37(1986)113 – 126.
E. Erkut and V. Verter, Hazardous materials logistics, in: Facility Location: A Survey of Applications and Methods, ed. Z. Drezner, Springer, New York, 1995, chapter 20.
F. Fischetti and P. Toth, An additive approach for the optimal solution of the prize-collecting Travelling Salesman Problem, in: Vehicle Routing: Methods and Studies, eds. B.L. Golden and A.A. Assad, North-Holland, Amsterdam, 1988.
J. Flynn and S. Ratick, A multiobjective hierarchical covering model for the essential air services program, Transp. Sci. 22(1988)139 – 147.
J.R. Goldberg, R. Dietrich, J.M. Cheng, M.G. Mitwasi, T. Valenzuela and E. Criss, Validating and applying a model for locating emergency medical vehicles in Tucson, AZ (case study), Eur. J. Oper. Res. 49(1990)308 – 324.
K.N. Groom, Planning emergency ambulance services, J. Oper. Res. Soc. 62(1977)323–339.
A.P. Hurter and M.G. Van Buer, The newspaper/distribution problem, J. of Bus. Logist. 17(1996)85 – 107.
P. Kolesar, Testing for vision loss in glaucoma suspects, Manag. Sci. 26(1980)439 – 450.
G. Laporte and S. Martello, The selective travelling salesman problem, Disc. Appl. Math. 26(1990)193 – 207.
C. Malandraki and M.S. Daskin, The maximum benefit Chinese postman problem and the maximum benefit travelling salesman problem, Eur. J. Oper. Res. 65(1993)193 – 234.
J.A. Mesa and T.B. Boffey, Location of extensive facilities in networks, Eur. J. Oper. Res. 95(1996)592 – 603.
G. Moore and C.S. ReVelle, The hierarchical service location problem, Manag. Sci. 28(1982)775 – 780.
L.S. Ochi, E.M. dos Santos, A.A. Montenegro and H. Maculan, Artificial genetic algorithms for the travelling purchaser problem, Proceedings of the Metaheuristics International Conference, Kluwer, Norwell, MA, 1995.
J.P. Osleeb and S. McLafferty, A weighted covering model to aid in Dracunculiasis eradication, Papers Regional Science Assoc. 71(1992)243 – 257.
J. Repede and J. Bernardo, Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky, Eur. J. Oper. Res. 75(1994)567 – 581.
C.S. ReVelle, K.E. Rosing and T.B. Boffey, The anchored network covering problem, Working Paper, MBB97-03, Department of Mathematical Sciences, Liverpool University, 1997.
N.G.F. Sancho, The hierarchical network design problem network design problem with multiple primary paths, Eur. J. Oper. Res. 96(1996)323– 328.
D.A. Schilling C.S. ReVelle, J.L. Cohon and D.J. Elzinga, Some models for fire protection locational decisions, Eur. J. Oper. Res. 5(1979)1 – 7.