硬时间窗角度分析的外卖配送车辆路径问题

本文对带硬时间窗的外卖配送车辆路径问题的研究成果主要可以概括为以下几点：（1）根据外卖配送的特点，建立了带硬时间窗的外卖配送车辆路径问题的数学模型；（2）设计了两种求解算法。借鉴生产排序中工序按最迟时间开工还是最早时间开工的思路，设计了两种求解算法，一种尽可能晚地规划订单路径，一种尽可能早地规划订单路径
第 1 章 绪论

1.1 研究背景及意义

  从 2010 年网络外卖订餐出现以来，快餐外卖在餐饮业中的比重逐步增大，成为餐饮业新生发展力量。如图 1-1 所示：在 2016 年我国的餐饮外卖市场规模已经达到 1662 亿人民币，占餐饮行业整体的 5.3%，外卖市场整体交易额在 2017 年达到 2052 亿人民币，这个成绩比上年同期增长了 23.5%,2018 年达 2430 亿人民币，同比增长 18.4%。自 2010 年外卖市场诞生以来，市场规模一直保持高速增长，但 2014 年以后增速逐渐放缓。

在经历过萌芽期、发展期、扩张期的市场竞争之后，目前快餐外卖正在进入相对稳定的成熟期，企业之间的竞争已经转向了提高服务水平和降低配送成本，更多的企业开始关注于配送服务的优化[1]。完善的配送系统、合理的配送路径以及高效的配送效率等都是提高配送服务质量、提升顾客满意度、降低配送成本的重要因素。

1.2 国内外研究现状

  车辆路径问题(Vehicle Routing Problem, VRP) [2]是指对一定数量的特定客户，规划出合适的配送车辆行驶路线，使配送车辆从配送中心出发，按照确定线路有序经过所有客户并最终返回配送中心，同时在满足一定的约束条件下，使得成本最小、行驶里程最短、使用车辆数最少或所耗时间最少等目的的一类问题。外卖配送中的车辆路径问题属于带时间窗的动态车辆路径问题。1959 年著名学者 Dantzig 和 Ramser[3]首次提出车辆路径问题(Vehicle Routing Problem,VRP)。在早期的 VRP 研究[4-12]中，绝大部分是基于确定性信息条件下建立的静态车辆路径问题(Static vehicle routing problem,SVRP)，但在实际的配送过程中存在着大量的不确定性因素，SVRP 模型很难有效地指导企业的实际配送作业。因此就需要进一步研究动态车辆路径问题（Dynamic vehicle routing problem, DVRP）。DVRP 的研究最早是由 Psaraftis[13]于 1988 年提出的,随后，Bertsimas 等[14-15]、Psaraftis[16]、

Bertsimas 等[17]、Gendreau 等[18]对 DVRP 的内涵和特征作了进一步研究。目前在 DVRP 领域已有一定数量的研究文献及综述论文[16,19-23]。在 DVRP 中，主要的动态要素包括：动态需求、动态的路段行驶时间、动态的服务车辆等[23]。根据动态要素及其特征的不同，现有文献研究的 DVRP 主要分为以下 3 种类型：基于动态需求的 VRP(Dynamic demand based VRP,DDVRP)、基于实时交通信息的VRP(Real-time traffic information based VRP,RTVRP)、基于动态需求和实时交通信息的VRP(Dynamic demand & real-time traffic information based VRP,DDRVRP)。

第 2 章 外卖配送现状及存在问题

2.1 外卖市场发展历程

  研究外卖的历史，可以将外卖的发展史分为“打包”、“电话订餐”、“网络订餐”、“平台订餐”几个阶段。“打包”可以看作是“外卖”的雏形，但通常意义上的打包多是指顾客进店购买后带回家食用或堂食后将剩余部分带回家食用，与现代意义上的“外卖”有所不同。随着通信技术的发展，电话订餐逐渐兴起，为了方便酒店备餐，减少不必要的候餐时间，顾客可通过电话提前订餐。后又有顾客将餐食打包带回家食用，形成实际意义上的“外卖”。电话订餐时顾客不必亲自前往饭店，而只需打电话给商家预定餐食，饭店制作完成后送给顾客，进一步方便了顾客用餐。电话和手机等通讯工具的广泛普及，使得电话订餐逐渐兴起并快速发展。相比于堂食和打包，电话订餐以其无需上门的优势，大大刺激了外卖行业的发展。互联网的普及，进一步刺激了外卖行业的发展。伴随互联网的普及。网络购物等新型购物形式诞生，而后网络订餐应运而生。随着智能手机的迅猛发展，移动互联网形成了新的浪潮，对各行各业产生了深远影响。其中最引人注目的，便是改变了餐饮形态的“美团外卖”等外卖订购平台。这些平台一方面方便了人们的生活，另一方面也使得外卖行业得以成长为千亿级别的市场，成为国民经济发展中的一块重要拼图。

相较国外外卖行业的发展，国内外卖行业发展起步较晚，但势头迅猛。以 2010 年 3月，美团网成立作为标志，外卖仍可算作是一个新兴行业，近十年才大规模兴起。虽然我国外卖市场形成规模的时间点相较于国外来说较晚，但其发展势头不容小觑。外卖行业从各外卖平台贴钱吸引商家入驻，到如今各商家付费入驻外卖平台的转变，不仅拓宽了商家商品的销售渠道，也改变了消费者的消费习惯，从这些方面来看我国外卖市场相关各方面的增长速度都是国外外卖企业无法比拟的。国外的外卖市场从起步到成熟，离不开国外学者大量的研究，他们的研究对象主要集中在成功的外卖商业模式和平台，这些研究为商家提供了准确的营销管理方案，促进了餐饮行业和外卖行业的共赢局面。而由于我国外卖行业的规模成型较晚，外卖行业相关研究也多集中在最近几年，并且研究的焦点大都是关于外卖行业现状、发展方向、商业模式等方面，对配送方面的研究非常少。其中对配送过程中路径规划的相关研究则是少之又少，对动态需求下带硬时间窗限制的外卖配送问题的研究更是几乎没有。这些研究都只是针对外卖行业中各企业如今经营模式现状以及今后的发展方向提出的建议和意见，研究程度不够深入。目前外卖行业迎来了大批的竞争者，相互竞争激烈，该行业俨然有成为红海的趋势。关于外卖企业之间外卖配送问题的研究少之又少，外卖企业要在在现有激烈竞争环境中夺取市场份额，优化外卖配送过程就是企业获取竞争优势的必要条件之一。

2.2 外卖特点

  “外卖”这一商业模式的组成环节主要包括顾客线上下单并付款、商家接单、线下配送、顾客用餐并线上评价等一系列动作。该模式下，商家通过线上平台展示餐品、营销推广，顾客通过网络平台下单，使互联网成为交易平台；然后线下配送给顾客用餐。这种线上线下相结合，既涉及线上又涉及线下，使消费者实现线上消费，线下享受相关服务的模式，就是所谓的 O2O（Online To Offline）模式。外卖形式下，顾客订餐交易主要由顾客线上下单、商家接单和线下配送几个部分。配送是外卖 O2O 的一个重要的组成部分，外卖配送有许多不同与传统物流配送的特点[48-51]，具体包括：

(1) 时效性要求高。相较于其他车辆路径问题，外卖配送的时效性要求很高。经过对美团外卖、饿了么外卖等外卖平台以及肯德基宅急送、麦当劳麦乐送等外卖平台的调研，不难发现多数平台从下单到送达一般要求在 30—60 分钟内完成，预定要求送达的准时性也在分钟级。这是由餐饮服务行业的特殊性决定的，对于餐品而言，时间对商品的质量会有重要影响。

(2) 高峰期突出。外卖订单一般会在正常用餐时间大量生成，而在非用餐时间段内则较少生成，相应的，高峰时间段内的制作、配送压力较大。当然，还有一些奶茶、甜点等非正餐属性的外卖商品，相对而言高峰期没有那么突出。但总体来看，外卖行业明天的高峰期非常明显。这也是由于外卖行业的特殊性决定的。

第 3 章 车辆路径问题概述..................................................................................................... 14

3.1 静态车辆路径问题.................................................................................................... 14

3.2 动态车辆路径问题.................................................................................................... 15

3.3 外卖配送中车辆路径规划的特点............................................................................. 16

3.4 车辆路径问题求解算法简介 .................................................................................... 16

第 4 章 带硬时间窗的外卖配送车辆路径问题的数学模型................................................... 20

4.1 问题描述................................................................................................................... 20

4.2 基本假设................................................................................................................... 20

4.3 模型构建................................................................................................................... 21

4.4 本章小结................................................................................................................... 23

第 5 章 带硬时间窗的外卖配送车辆路径问题的求解算法................................................... 24

5.1 算法设计................................................................................................................... 24

5.2 算例求解................................................................................................................... 29

5.3 实验结果分析 ........................................................................................................... 32

5.4 本章小结................................................................................................................... 34

第 6 章 求解算法的性能研究................................................................................................. 36

6.1 算例设计................................................................................................................... 36

6.2 算例验证................................................................................................................... 40

6.3 优劣性比较............................................................................................................... 44

6.4 原因分析及适用范围研究........................................................................................ 45

第 6 章 求解算法的性能研究

6.1 算例设计

  为进一步验证算法的优劣性，需设计更多算例进行求解。本文所验算算例分为两类：一类是根据现实生活中的实际外卖订单，进行筛选整理，形成有效算例；另一类是对现有VRP 问题算例库进行整理，形成契合外卖配送问题的有效算例。然后分别利用设计的求解算法进行求解验算。

6.1.1 任务点集的构建

为了更好验证算法的优劣性，通过调查研究，本文借鉴 Solomon 算例库中的部分算例的任务点坐标，进行处理，构建本文算例的任务点集。由于 Solomon 算例中 R 系列、C 系列、RC 系列的任务点坐标值均各自相同，所以本文提取 R101、C101、RC101 的任务点坐标值，并将每组算例中的任务点坐标分为每组包含 50 个任务点的两组任务点集，得到的任务点集中各点坐标详见附录 A，其中部分点的坐标如表 6-1 所示：

第 7 章 结论与展望

7.1 结论

本文对带硬时间窗的外卖配送车辆路径问题的研究成果主要可以概括为以下几点：（1）根据外卖配送的特点，建立了带硬时间窗的外卖配送车辆路径问题的数学模型；（2）设计了两种求解算法。借鉴生产排序中工序按最迟时间开工还是最早时间开工的思路，设计了两种求解算法，一种尽可能晚地规划订单路径，一种尽可能早地规划订单路径。3）设计了大量算例，并利用 MATLAB 对两种算法优劣性进行了研究分析，最终发现可以依照不同情形下的外卖配送车辆路径问题的特点，选用不同的求解算法。如果配送人工成本高，想要尽可能减少路径数目，则一般情况下建议优先选择算法二。如果配送成本低，主要考虑总路径的长短，则当某一区域内短时间内有聚集性下单时，优先考虑算法二；当任务点分布较分散，且相邻时间所下订单的配送位置相距较远时，可优先考虑算法。