The Periodical Vehicle Routing Problem: Research Overview and Practical Application to a South German Fast Food Restaurant

Mémoire (de fin d'études) , 2005 , 156 Pages , Note: 1,3

Gestion d'entreprise - Généralités

In the middle of May 1997 Gerd Raupeter, CEO of McDonald’s Deutschland Inc. (Mc Donald’s Germany Inc.), had to announce that some restaurants were sold out of shrimps1. The keen customer’s demand for this kind of seafood already exceeded the expected forecasts one week after starting the ongoing “Fisch-Wochen” (fish-weeks) mission. As these circumstances highlighted an accurate product choice for the fast food corporation Mr. Raupeter has nevertheless been pleased about it.
Otherwise, such an awkward situation could be prevented by developing a demand-driven scheduling for each restaurant in the future. The Periodic(al) Vehicle Routing Problem (PVRP) seems to be a tailor-made solution for the reason that exact planning has to be done and “…delivery routes must be constructed over a period of time (for example, multiple days).”
Observations and analyzes in the literature in most of the industries deal with a constant demand for goods and with only one good. Moreover the one-of-a-kind client prevails. But for the application of the PVRP to the gastronomy there are some exceptions to be considered. As this paper presents a solution approach of the delivery problem for the fast-food industry in South Germany, there are products to be transported consisting of diverse components. Although there are nearly identical opening hours, the eating places – the clientele to be delivered - due to their irregular demand for food and beverages are varying from the unique purchaser. Another singularity lies in the conformity of the foodstuff which is reflected in the comparability of each restaurant. Therefore the enduring solution approach will be done in a sample of some fast food restaurants.
This paper herein is organized as follows. In the second and third chapter, various theories that could lead depots how to organize its delivery are reviewed, with an emphasis on the Vehicle Routing Problem (VRP) as well as the PVRP.

Inhaltsverzeichnis (Table of Contents)

• Introduction
• The Vehicle Routing Problem (VRP)
• The basic developments of the Vehicle Routing Problem
• The Bin Packing Problem (BPP)
• The Traveling Salesman Problem (TSP)
• The Vehicle Routing Problem (VRP)
• The mathematical formulation of the Vehicle Routing Problem
• Different kinds of the Vehicle Routing Problem
• The periodic(al) vehicle routing problem (PVRP)
• The classical PVRP
• Pioneer Work for the PVRP
• The concept of Beltrami and Bodin
• The concept of Russel and Igo
• Additional work in the 1980s and 1990s
• The concept of Christofides and Beasley
• The concept of Russel and Gribbin
• The concept of Chao, Golden, and Wasil
• The concept of Cordeau, Gendreau, and Laporte
• Applied research of today
• The concept of Shih and Chang
• The concept of Angelelli and Speranza
• The concept of Blakeley and Knolmajer
• The concept of Alegre, Laguna, and Pacheco
• The fast food industry and its reasons of success
• McDonald's
• The beginning of McDonald's
• The expansion of McDonald's
• Burger King
• Historical facts
• The expansion of Burger King
• Subway
• The beginning
• The expansion and the principles of shock frosting
• The health factor and the German challenge
• The virtual fast-food chain and the Optimization Programming Language (OPL)
• The virtual fast-food chain
• The locations of the virtual fast-food chain
• Distances, the resulting fuel costs, and the travel time
• Inventory Costs
• Trucks and driving costs
• Trucks
• Trucker's loans
• Opening hours
• Different categories of the restaurants
• Attendance
• Demand of the restaurants
• Range of products
• Total delivery quantity
• The Optimization Programming Language (OPL)
• The development of the Optimization Programming Language
• The creation of the mathematical model for the virtual fast-food chain
• Symbols needed for the creation of the mathematical model
• Objective function
• Side conditions

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This diploma thesis aims to explore the Periodic Vehicle Routing Problem (PVRP) by examining its historical development, key concepts, and practical application in the context of a virtual fast-food chain. Through a comprehensive analysis of the PVRP and its variants, the thesis seeks to understand the challenges associated with optimizing delivery routes for a multi-location fast-food business.

• The historical development and evolution of the Vehicle Routing Problem (VRP) and its variations, including the Periodic Vehicle Routing Problem (PVRP)
• The application of the PVRP in optimizing delivery routes for a virtual fast-food chain, considering factors like delivery frequency, inventory costs, and travel time
• The use of mathematical modeling and the Optimization Programming Language (OPL) to solve the PVRP and determine optimal delivery routes
• The significance of the PVRP in the fast-food industry, and its potential for improving delivery efficiency, reducing costs, and enhancing customer satisfaction

Zusammenfassung der Kapitel (Chapter Summaries)

• Introduction: This chapter sets the stage for the thesis, providing a brief overview of the Vehicle Routing Problem (VRP) and its importance in logistics and operations management. It also introduces the concept of the Periodic Vehicle Routing Problem (PVRP) and its specific applications in real-world scenarios.
• The Vehicle Routing Problem (VRP): Chapter 2 delves into the origins of the VRP, tracing its development from early concepts like the Bin Packing Problem and the Traveling Salesman Problem. The chapter also discusses different types of VRPs, focusing on the core principles and mathematical formulations that are relevant to the PVRP.
• The periodic(al) vehicle routing problem (PVRP): Chapter 3 explores the intricacies of the PVRP, defining the classical PVRP and highlighting its key characteristics. The chapter then delves into pioneering work that laid the foundation for the PVRP, discussing contributions from Beltrami and Bodin, Russel and Igo, and others. Further, it analyzes subsequent research conducted in the 1980s and 1990s, examining the concepts developed by Christofides and Beasley, Russel and Gribbin, Chao, Golden, and Wasil, and Cordeau, Gendreau, and Laporte. Finally, the chapter touches upon contemporary research, including the work of Shih and Chang, Angelelli and Speranza, Blakeley and Knolmajer, and Alegre, Laguna, and Pacheco.
• The fast food industry and its reasons of success: Chapter 4 examines the fast-food industry, specifically focusing on three major players: McDonald's, Burger King, and Subway. It explores the historical development, growth strategies, and key factors contributing to their success. The chapter analyzes the various aspects of each company, including their origins, expansion strategies, and market positioning.
• The virtual fast-food chain and the Optimization Programming Language (OPL): Chapter 5 introduces a virtual fast-food chain, which serves as a case study for applying the PVRP. It describes the locations, distances, fuel costs, travel time, and demand characteristics of this virtual chain. Additionally, the chapter analyzes the inventory costs, truck and driving costs, and opening hours of the virtual fast-food chain. The chapter also explores the Optimization Programming Language (OPL) and its potential in solving complex optimization problems like the PVRP.
• The creation of the mathematical model for the virtual fast-food chain: Chapter 6 delves into the process of creating a mathematical model for the virtual fast-food chain, specifically designed to address the PVRP. This chapter outlines the symbols used in the model and defines the objective function and side conditions.

Schlüsselwörter (Keywords)

This thesis focuses on the Periodic Vehicle Routing Problem (PVRP), exploring its history, concepts, and practical applications within the fast-food industry. The analysis utilizes mathematical modeling and the Optimization Programming Language (OPL) to solve complex routing problems, optimizing delivery routes and minimizing associated costs. The thesis examines different types of VRPs and various research contributions from prominent figures in the field. Key concepts include delivery frequency, inventory costs, travel time, truck and driving costs, and customer satisfaction. Through a case study of a virtual fast-food chain, the thesis sheds light on the potential of the PVRP in optimizing delivery processes for multi-location businesses.

• Université: University of Augsburg
• Note: 1,3
• Auteur: Claus Friedrich (Auteur)
• Année de publication: 2005
• Pages: 156
• N° de catalogue: V52834
• ISBN (ebook): 9783638484367
• Langue: anglais
• mots-clé: Periodical, Vehicle, Routing, Problem, Research, Overview, Practical, Application, South, German, Fast, Food, Restaurant