Skip to main content
SpringerLink
Log in

Planning for meals-on-wheels: algorithms and application

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

Home-delivered meals provision, also known as meals-on-wheels, is a volunteer-staffed activity for which little strategic planning is performed. We develop a Memetic Algorithm to solve the Home Delivered Meals Location-Routing Problem. This planning model addresses facility location, allocation of demand to facilities, and design of delivery routes, while balancing efficiency and effectiveness considerations. The case study presented on a large data set shows how trade-off curves, which are very useful for decision making, can be obtained by the method developed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5

Similar content being viewed by others

References

  • Albareda-Sambola M, Diaz J and Fernández E (2005). A compact model and tight bounds for a combined location-routing problem. Computers and Operations Research 32 (3): 407–428.

    Article  Google Scholar 

  • Barreto S, Ferreira C, Paixao J and Santos B (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research 179 (3): 968–977.

    Article  Google Scholar 

  • Bartholdi J, Platzman L, Collins R and Warden W (1983). A minimal technology routing system for meals on wheels. Interfaces 13 (3): 1–8.

    Article  Google Scholar 

  • Berger R (1997). Location-routing models for distribution system design. Unpublished Dissertation, Northwestern University, Department of Industrial Engineering and Management Sciences, Evanston, IL, USA.

  • Bookbinder J and Reece K (1988). Vehicle routing considerations in distribution system design. European Journal of Operational Research 37 (2): 204–213.

    Article  Google Scholar 

  • Bruns A and Klose A (1995). An iterative heuristic for location-routing problems based on clustering. In: Proceedings of the Second International Workshop on Distribution Logistics, The Netherlands, pp 1–6.

    Google Scholar 

  • Bruns A and Klose A (1997). A ‘locate first—route second’ heuristic for a combined location-routing problem. In: Zimmermann U, Derings U, Gaul W, Möhring RH and Schuster KP (eds). Operations Research Proceedings 1996. Springer; Berlin Heidelberg: New York, pp 49–54.

    Chapter  Google Scholar 

  • Caballero R, Gonzalez M, Guerrero F, Molina J and Paralera C (2007). Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia. European Journal of Operational Research 177 (3): 1751–1763.

    Article  Google Scholar 

  • Chan Y, Carter W and Burnes M (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Computers and Operations Research 28 (8): 803–826.

    Article  Google Scholar 

  • Coello C (1999). A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge and Information systems 1 (3): 129–156.

    Google Scholar 

  • Coello C and Romero C (2002). Evolutionary algorithms and multiple objective optimization. In: Ehrgott M and Gandibleux X (eds). Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers: New York.

    Google Scholar 

  • Coello Coello C and Lamont G (2005). An introduction to multi-objective evolutionary algorithms and their applications. In: Coello Coello CA and Lamont GB (eds). Applications of Multi-Objective Evolutionary Algorithms. World Scientific Publishing: Singapore, pp 1–28.

    Google Scholar 

  • Cornuejols G, Fisher M and Nemhauser G (1977). Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Science 23 (8): 789–810.

    Article  Google Scholar 

  • Deb K (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley: New York.

    Google Scholar 

  • Deb K, Pratap A, Agarwal S and Meyarivan T (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2): 182–197.

    Article  Google Scholar 

  • Dunn K (2008). Euclidian traveling salesman problem solver. http://fly.hiwaay.net:8000/~kdunn/problems/tsp.shtml.

  • Gorr W, Johnson M and Roehrig S (2001). Spatial decision support system for home-delivered services. Journal of Geographic Systems 3 (2): 181–197.

    Article  Google Scholar 

  • Gunes C, van Hoeve W and Tayur S (2010). Vehicle routing for food rescue programs: A comparison of different approaches. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems 6140:176–180.

    Article  Google Scholar 

  • Hansen P, Hegedahl B, Hjortkjaer S and Obel B (1994). A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research 76 (1): 111–127.

    Article  Google Scholar 

  • Johnson M, Gorr W and Roehrig S (2002). Location/allocation/routing for home-delivered meals provision: Models & solution approaches. International Journal of Industrial Engineering 9 (1): 45–56.

    Google Scholar 

  • Jones D, Mirrazavi S and Tamiz M (2002). Multi-objective meta-heuristics: An overview of the current state-of-the-art. European Journal of Operational Research 137 (1): 1–9.

    Article  Google Scholar 

  • Karp RM (1972). Reducibility among combinatorial problems. In: Miller RE and Thatcher JW (eds). Complexity of Computer Computations: Proceeding of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, Plenum Press: New York, NY, pp. 85–103.

    Chapter  Google Scholar 

  • Knowles J and Corne D (1999). The Pareto archived evolution strategy: A new baseline algorithm for Pareto multiobjective optimisation. In: Evolutionary Computation, 1999 CEC 99. Proceedings of the 1999 Congress on. Vol. 1, pp 98–105.

    Article  Google Scholar 

  • Knowles J and Corne D (2000). Approximating the nondominated front using the Pareto Archived Evolution Strategy. Evolutionary Computation 8 (2): 149–172.

    Article  Google Scholar 

  • Laporte G and Dejax P (1989). Dynamic location-routeing problems. Journal of the Operational Research Society 40 (5): 471–482.

    Article  Google Scholar 

  • Laporte G and Nobert Y (1981). Exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research 6 (2): 224–226.

    Article  Google Scholar 

  • Laporte G, Nobert Y and Pelletier P (1983). Hamiltonian location problems. European Journal of Operational Research 12 (1): 82–89.

    Article  Google Scholar 

  • Laporte G, Nobert Y and Arpin D (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research 6 (9): 291–310.

    Article  Google Scholar 

  • Laporte G, Nobert Y and Taillefer S (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science 22 (3): 161–172.

    Article  Google Scholar 

  • Laporte G, Louveaux F and Mercure H (1989). Models and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research 39 (1): 71–78.

    Article  Google Scholar 

  • Lenstra J and Kan AR (1981). Complexity of vehicle routing and scheduling problems. Networks 11 (2): 221–227.

    Article  Google Scholar 

  • Lin C and Kwok R (2006). Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. European Journal of Operational Research 175 (3): 1833–1849.

    Article  Google Scholar 

  • Lin C, Chow C and Chen A (2002). A location-routing-loading problem for bill delivery services. Computers & Industrial Engineering 43 (1–2): 5–25.

    Article  Google Scholar 

  • Lin S (1965). Computer solutions of the traveling salesman. Bell System Technical Journal 44 (10): 2245–2269.

    Article  Google Scholar 

  • Lopes R, Barreto S, Ferreira C and Santos B (2008). A decision-support tool for a capacitated location-routing problem. Decision Support Systems 46 (1): 366–375.

    Article  Google Scholar 

  • Madsen O (1983). Methods for solving combined two level location-routing problems of realistic dimensions. European Journal of Operational Research 12 (3): 295–301.

    Article  Google Scholar 

  • Medaglia A, Villegas J and Rodrguez-Coca D (2009). Hybrid biobjective evolutionary algorithms for the design of a hospital waste management network. Journal of Heuristics 15 (2): 153–176.

    Article  Google Scholar 

  • Michalewicz Z (1996). Genetic Algorithms+Data Structures=Evolution Programs. Springer: New York.

    Book  Google Scholar 

  • Nagy G and Salhi S (1996). Nested heuristic methods for the location-routeing problem. Journal of the Operational Research Society 47 (9): 1166–1174.

    Article  Google Scholar 

  • Nagy G and Salhi S (2007). Location-routing: Issues, models and methods. European Journal of Operational Research 177 (2): 649–672.

    Article  Google Scholar 

  • Or I and Pierskalla W (1979). A transportation location-allocation model for regional blood banking. IIE Transactions 11 (2): 86–95.

    Google Scholar 

  • Pariazar M, Sir MY and Root S (2012). Robust supply chain design considering correlated failures and inspection. University of Missouri-Columbia: Columbia, MO, Working Paper.

    Google Scholar 

  • Perl J and Daskin M (1985). A warehouse location-routing problem. Transportation Research 19 (5): 381–396.

    Article  Google Scholar 

  • Prins C, Prodhon C and Calvo R (2006a). A memetic algorithm with population management (MA∣PM) for the capacitated location-routing problem. In: Jens G and Günther R (eds). Evolutionary Computation in Combinatorial Optimization: 6th European Conference, EvoCOP 2006, Budapest, Hungary, April 10–12, 2006: Proceedings. Springer: New York.

    Google Scholar 

  • Prins C, Prodhon C and Calvo R (2006b). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR: A Quarterly Journal of Operations Research 4 (3): 47–64.

    Article  Google Scholar 

  • Prins C, Prodhon C, Ruiz A, Soriano P and Wolfler Calvo R (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science 41 (4): 470.

    Article  Google Scholar 

  • Renaud J, Laporte G and Boctor F (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers and Operations Research 23 (3): 229–235.

    Article  Google Scholar 

  • Solak S, Scherrer C and Ghoniem A (2012). The stop-and-drop problem in nonprofit food distribution networks. Annals of Operations Research: doi: 10.1007/s10479-012-1068-7.

  • Tuzun D and Burke L (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research 116 (1): 87–99.

    Article  Google Scholar 

  • Wong D and Meyer J (1993). A spatial decision support system approach to evaluate the efficiency of a meals-on-wheels program. The Professional Geographer 45 (3): 332–341.

    Article  Google Scholar 

  • Wu T, Low C and Bai J (2002). Heuristic solutions to multi-depot location-routing problems. Computers and Operations Research 29 (10): 1393–1415.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Michigan State University, East Lansing, MI, USA

    H Yildiz

  2. University of Massachusetts Boston, Boston, MA, USA

    M P Johnson

  3. Carnegie Mellon University, Pittsburgh, PA, USA

    S Roehrig

Authors
  1. H Yildiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M P Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S Roehrig
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H Yildiz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yildiz, H., Johnson, M. & Roehrig, S. Planning for meals-on-wheels: algorithms and application. J Oper Res Soc 64, 1540–1550 (2013). https://doi.org/10.1057/jors.2012.129

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.129

Keywords

Search

Navigation