Meal Delivery Optimisation for the Restaurant Chain

Abstract

The recognition of meal delivery service solutions in restaurant chain enterprises is like a diamond in the rough, as these solutions are frequently undisclosed by companies, contributing to their relative obscurity in the field of transportation optimisation research. Inspired by the potential challenges and opportunities that the COVID-19 pandemic may present to chain catering food delivery services, this thesis proposes two innovative self-operated meal delivery solutions for restaurant chain companies with practical applicability, named as Self-Operated Coordinative service Solution (SOCSS) and Self-Operated Alternative service Solution (SOASS), respectively. Both of these solutions can be abstracted as generalisations of the Pickup and Delivery Problem with Time Window (PDPTW). In the PDPTW, vehicles with limited capacities are assigned to fulfill customer requests, each of which consists a pair of pickup and delivery, subject to precedence (i.e., the pickup have to be made before the delivery) and pairing (i.e., both pickup and delivery must be performed by the same vehicle) as well as time window constraints. If more practical extensions are included, such problems can be referred to the Rich Vehicle Routing Problems (RVRPs).

After observing the avoidable inefficiencies and personnel redundancies in the widespread applied End-to-End Exclusive Service Solution (3ESS), we underscore the significance of integrating courier resources along the chain in the SOCSS to allow couriers to pickup new meal orders from different restaurants of the chain, and for the first time design a novel Branch-and-Price-and-Cut (BPC) approach by introducing an adaptive implicit enumeration inspired subproblem solver and incorporating two categories of valid inequalities for exactly solving the SOCSS. The pandemic-induced surge in third-party Online Food Ordering and Delivery (OFOD) platforms has propelled them to a dominant position in the competitive environment compared with participating restaurants. To curb the monopoly of these platforms, we recommend that restaurant chain companies adopt the SOASS strategy using a crowdsourcing courier recruitment model. By applying predetermined filtering criteria to batch homogeneous meal orders, this thesis presents a two-stage Mixed Integer Linear Programming (MILP) model and a tailored Adaptive Variable Neighborhood Search (AVNS) algorithm to solve the SOASS comprehensively.

The effectiveness and superiority of the SOCSS and SOASS are demonstrated via thorough numerical experiments, furnishing valuable theoretical guidance for decision-makers of restaurant chain enterprises in devising new market strategies.