IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v45y2011i3p413-434.html
   My bibliography  Save this article

The Mobile Facility Routing Problem

Author

Listed:
  • Russell Halper

    (Applied Math and Scientific Computation Program, University of Maryland, College Park, Maryland 20742)

  • S. Raghavan

    (Smith School of Business and Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

Abstract

In many applications, ranging from cellular communications to humanitarian relief logistics, mobile facilities are used to provide a service to a region with temporal and spatially distributed demand. This paper introduces the mobile facility routing problem (MFRP), which seeks to create routes for a fleet of mobile facilities that maximizes the demand serviced by these mobile facilities during a continuous-time planning horizon. In this setting, demand is produced by discrete events at rates that vary over time. Mobile facilities can be positioned at discrete locations to provide service to nearby events. In addition, mobile facilities can be relocated at any time, although the relocation times are significant in relation to the length of the planning horizon. The demand serviced by a mobile facility depends on the arrival and departure times at each location it visits. Although the MFRP is NP-hard, the optimal route for a single mobile facility can be computed in polynomial time. We describe three heuristics for creating routes for the fleet of mobile facilities and evaluate their performance. Our results demonstrate that these heuristics produce high-quality routes for mobile facilities, especially in scenarios where the demand for service changes significantly over time.

Suggested Citation

  • Russell Halper & S. Raghavan, 2011. "The Mobile Facility Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 413-434, August.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:3:p:413-434
    DOI: 10.1287/trsc.1100.0335
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0335
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0335?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Current, J. R. & Re Velle, C. S. & Cohon, J. L., 1985. "The maximum covering/shortest path problem: A multiobjective network design and routing formulation," European Journal of Operational Research, Elsevier, vol. 21(2), pages 189-199, August.
    2. George O. Wesolowsky, 1973. "Dynamic Facility Location," Management Science, INFORMS, vol. 19(11), pages 1241-1248, July.
    3. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    4. Tony J. Van Roy & Donald Erlenkotter, 1982. "A Dual-Based Procedure for Dynamic Facility Location," Management Science, INFORMS, vol. 28(10), pages 1091-1105, October.
    5. George O. Wesolowsky & William G. Truscott, 1975. "The Multiperiod Location-Allocation Problem with Relocation of Facilities," Management Science, INFORMS, vol. 22(1), pages 57-65, September.
    6. John R. Current & David A. Schilling, 1989. "The Covering Salesman Problem," Transportation Science, INFORMS, vol. 23(3), pages 208-213, August.
    7. John Current & Hasan Pirkul & Erik Rolland, 1994. "Efficient Algorithms for Solving the Shortest Covering Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 317-327, November.
    8. Erlenkotter, Donald, 1981. "A comparative study of approaches to dynamic location problems," European Journal of Operational Research, Elsevier, vol. 6(2), pages 133-143, February.
    9. Brotcorne, Luce & Laporte, Gilbert & Semet, Frederic, 2003. "Ambulance location and relocation models," European Journal of Operational Research, Elsevier, vol. 147(3), pages 451-463, June.
    10. VAN ROY, Tony J. & ERLENKOTTER, Donald, 1982. "A dual-based procedure for dynamic facility location," LIDAM Reprints CORE 490, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Current, John R. & Schilling, David A., 1994. "The median tour and maximal covering tour problems: Formulations and heuristics," European Journal of Operational Research, Elsevier, vol. 73(1), pages 114-126, February.
    12. Ghiani, Gianpaolo & Guerriero, Francesca & Laporte, Gilbert & Musmanno, Roberto, 2003. "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies," European Journal of Operational Research, Elsevier, vol. 151(1), pages 1-11, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shahmoradi-Moghadam, Hani & Schönberger, Jörn, 2021. "Joint optimization of production and routing master planning in mobile supply chains," Operations Research Perspectives, Elsevier, vol. 8(C).
    2. Fadaki, Masih & Abareshi, Ahmad & Far, Shaghayegh Maleki & Lee, Paul Tae-Woo, 2022. "Multi-period vaccine allocation model in a pandemic: A case study of COVID-19 in Australia," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    3. Bayraktar, O. Baturhan & Günneç, Dilek & Salman, F. Sibel & Yücel, Eda, 2022. "Relief Aid Provision to En Route Refugees: Multi-Period Mobile Facility Location with Mobile Demand," European Journal of Operational Research, Elsevier, vol. 301(2), pages 708-725.
    4. Junxuan Li & Chelsea C. White, 2023. "Capacity planning in a decentralized autologous cell therapy manufacturing network for low-cost resilience," Flexible Services and Manufacturing Journal, Springer, vol. 35(2), pages 295-319, June.
    5. Duijzer, Lotty Evertje & van Jaarsveld, Willem & Dekker, Rommert, 2018. "Literature review: The vaccine supply chain," European Journal of Operational Research, Elsevier, vol. 268(1), pages 174-192.
    6. Satya S. Malladi & Alan L. Erera & Chelsea C. White, 2021. "Managing mobile production-inventory systems influenced by a modulation process," Annals of Operations Research, Springer, vol. 304(1), pages 299-330, September.
    7. Chenmei Teng & Poshan Yu & Liwen Liu, 2024. "A cooperative optimization model and enhanced algorithm for guided strategies in emergency mobile facilities," Palgrave Communications, Palgrave Macmillan, vol. 11(1), pages 1-11, December.
    8. Salman, F. Sibel & Yücel, Eda & Kayı, İlker & Turper-Alışık, Sedef & Coşkun, Abdullah, 2021. "Modeling mobile health service delivery to Syrian migrant farm workers using call record data," Socio-Economic Planning Sciences, Elsevier, vol. 77(C).
    9. Ece Zeliha Demirci & Nesim Kohen Erkip, 2020. "Designing intervention scheme for vaccine market: a bilevel programming approach," Flexible Services and Manufacturing Journal, Springer, vol. 32(2), pages 453-485, June.
    10. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    2. Vatsa, Amit Kumar & Ghosh, Diptesh, 2014. "Tabu Search for Multi-Period Facility Location: Uncapacitated Problem with an Uncertain Number of Servers," IIMA Working Papers WP2014-11-03, Indian Institute of Management Ahmedabad, Research and Publication Department.
    3. Vatsa, Amit Kumar, 2014. "Multi-Period Facility Location Problem with an Uncertain Number of Servers," IIMA Working Papers WP2014-02-06, Indian Institute of Management Ahmedabad, Research and Publication Department.
    4. Current, John & Ratick, Samuel & ReVelle, Charles, 1998. "Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach," European Journal of Operational Research, Elsevier, vol. 110(3), pages 597-609, November.
    5. Tang, Lianhua & Li, Yantong & Bai, Danyu & Liu, Tao & Coelho, Leandro C., 2022. "Bi-objective optimization for a multi-period COVID-19 vaccination planning problem," Omega, Elsevier, vol. 110(C).
    6. Xin Wang & Michael K. Lim & Yanfeng Ouyang, 2017. "A Continuum Approximation Approach to the Dynamic Facility Location Problem in a Growing Market," Transportation Science, INFORMS, vol. 51(1), pages 343-357, February.
    7. Güden, Hüseyin & Süral, Haldun, 2014. "Locating mobile facilities in railway construction management," Omega, Elsevier, vol. 45(C), pages 71-79.
    8. Sanjay Dominik Jena & Jean-François Cordeau & Bernard Gendron, 2015. "Dynamic Facility Location with Generalized Modular Capacities," Transportation Science, INFORMS, vol. 49(3), pages 484-499, August.
    9. Timothy J. Niblett & Richard L. Church, 2016. "The Shortest Covering Path Problem," International Regional Science Review, , vol. 39(1), pages 131-151, January.
    10. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    11. Allman, Andrew & Zhang, Qi, 2020. "Dynamic location of modular manufacturing facilities with relocation of individual modules," European Journal of Operational Research, Elsevier, vol. 286(2), pages 494-507.
    12. Mesa, Juan A. & Brian Boffey, T., 1996. "A review of extensive facility location in networks," European Journal of Operational Research, Elsevier, vol. 95(3), pages 592-603, December.
    13. Avella, P. & Benati, S. & Canovas Martinez, L. & Dalby, K. & Di Girolamo, D. & Dimitrijevic, B. & Ghiani, G. & Giannikos, I. & Guttmann, N. & Hultberg, T. H. & Fliege, J. & Marin, A. & Munoz Marquez, , 1998. "Some personal views on the current state and the future of locational analysis," European Journal of Operational Research, Elsevier, vol. 104(2), pages 269-287, January.
    14. Eric Delmelle & Jean-Claude Thill & Dominique Peeters & Isabelle Thomas, 2014. "A multi-period capacitated school location problem with modular equipment and closest assignment considerations," Journal of Geographical Systems, Springer, vol. 16(3), pages 263-286, July.
    15. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Reza Farahani & Zvi Drezner & Nasrin Asgari, 2009. "Single facility location and relocation problem with time dependent weights and discrete planning horizon," Annals of Operations Research, Springer, vol. 167(1), pages 353-368, March.
    17. A Başar & B Çatay & T Ünlüyurt, 2011. "A multi-period double coverage approach for locating the emergency medical service stations in Istanbul," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 627-637, April.
    18. António Antunes & Oded Berman & João Bigotte & Dmitry Krass, 2009. "A Location Model for Urban Hierarchy Planning with Population Dynamics," Environment and Planning A, , vol. 41(4), pages 996-1016, April.
    19. Shahzad Bhatti & Michael Lim & Ho-Yin Mak, 2015. "Alternative fuel station location model with demand learning," Annals of Operations Research, Springer, vol. 230(1), pages 105-127, July.
    20. Seifert, Ralf W. & Langenberg, Kerstin U., 2011. "Managing business dynamics with adaptive supply chain portfolios," European Journal of Operational Research, Elsevier, vol. 215(3), pages 551-562, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:45:y:2011:i:3:p:413-434. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.