The capacitated mobile facility location problem

S. Raghavan, Mustafa Sahin and F. Sibel Salman

European Journal of Operational Research, 2019, vol. 277, issue 2, 507-520

Abstract: The capacitated mobile facility location problem (CMFLP) arises in logistics planning of community outreach programs delivered via mobile facilities. It adds capacity restrictions to the mobile facility location problem introduced previously by Demaine et al. (2009), thereby extending the problem to a practical setting. In the problem, one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities while respecting capacities so that the weighted sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. We provide two integer programming formulations for the CMFLP. The first is on a layered graph, while the second is a set partitioning formulation. We prove that the linear relaxation of the set partitioning formulation provides a tighter lower bound to the CMFLP than the linear relaxation of the layered graph formulation. We then develop a branch-and-price algorithm on the set partitioning formulation. We find that the branch-and-price procedure is particularly effective both in terms of solution quality and running time, when the ratio of the number of clients to the number of facilities is small and the facility capacities are tight. Finally, we present two heuristic approaches for the CMFLP. One is a linear programming rounding heuristic, and the other is based on a natural decomposition of the problem on the layered graph.

Keywords: Location; Capacitated mobile facilities; Column generation; Branch-and-price; Local search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171930219X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:277:y:2019:i:2:p:507-520

DOI: 10.1016/j.ejor.2019.02.055

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().