摘要：随着我国经济日益快速发展，人们的生活节奏也随之加快，在蓬勃发展的今天人们在学习、工作忙忙碌碌中为了更快速便捷解决用餐问题，促使了近些年来各种各样的外卖企业的大量兴起，同时促使外卖行业的快速发展。在激烈的竞争中，外卖的配送效率和成本控制显得越来越重要，特别是在高校的快节奏生活中，外卖配送效率显得尤为重要，而外卖配送路线的选择往往决定着外卖配送的效率和成本的控制，本文以广州工商学院为例，为了让外卖配送的路线最优，应用了动态规划法进行外卖配送最优路线的研究。

　　关键词：动态规划法; 外卖; 最优路线; 高校

　　引言

　　外卖的O2O模式近年来的发展十分迅速，无论是各个发展城市的各种商圈，还是各高校的活动区域，到处都有外卖骑手的身影。然而，如何将配送的线路变得更加便捷，提高配送速度，减少顾客的等餐时间成为外卖行业需要思考的新方向。

　　由于高校食堂的集中性以及就餐高峰的拥挤，许多高校的大学生会选择手机点餐解决日常用餐问题。也正因如此，近年来的高校外卖需求增长迅速，毕竟以通过智能手机的外卖APP就可以享用附近的美食，这种方式非常的便捷，同时给高校师生就餐带来了方便又简单的体验，致使广大师生深爱这种方式。

　　配送线路的问题大多数行业都是通过后台系统经过人工智能合理规划路线，让配送工作人员减少多余的体力劳动付出。除此之外，在大幅度提高配送速度的同时还能达到高效的配送效率。

　　怎样让配送路线更为优化的问题最终是为了能给配送的工作人员提供更合理或最优的路线方案。许多学者都在相关方面进行调查研究，如有学者利用蚂蚁算法对外卖配送相关问题进行路径规划，提供最便捷的路径供使用者使用，也有许多精英协同进化遗传算法等应用到外卖配送的相关问题上。

　　本文在校园的外卖配送上，针对外卖配送的资源合理化的角度入手相关研究，从动态化的环境出发，结合商家、外卖平台、餐饮配送员和学校的管理等相关因素，以广州工商学院的三水校区为试验点，采用动态规划法对外卖配送问题，提出一种具有一定的线路顺序的路径优化方法，达到配送的人力资源合理利用，送餐时间更为快捷的效果。

　　一、高校外卖配送现状分析

　　(一)外卖平台

　　“美团外卖”、“饿了么”两大电商平台在外卖市场的激烈竞争中得以生存，占据了O2O模式下外卖平台百分之八十左右的份额，成为O2O模式下外卖平台的领军者。2017年，美团外卖总交易额达到1710亿;2018年3月23日科技部在北京国际会议中心第五会议厅召开新闻发布会，正式发布《2017年中国独角兽企业发展报告》，饿了么以五十五亿美元的估值排名第十六位;而“饿了么”与“美团外卖”的目标顾客均为高校学生、青年白领，学生人口密度大，推广成本低，且随着时代发展，生活物质条件逐步改善，学生的饮食口味变得越来越挑剔，高校学生对外卖的需求也越来越大。消费者在选择外卖平台消费时，偏向于选择有资质的外卖平台，以保障食品安全及用户信息安全，“美团外卖”、“饿了么”成为了众多外卖消费者的选择。

　　(二)配送方式

　　学校外卖的配送主要有3种形式

　　1.商家自营配送。点餐者从消费端下单后，经由O2O外卖平台传达至商家，商家承担起了备餐、配送的任务，将包装好的食物送至点餐者手中。大多数商家位于学校附近，配送者对校园路线十分了解，在配送过程中会选择最为“经济”的路线，用最短的时间配送最多的单数。这种配送方式带给消费者的体验因商家而异，配送效率越高的商家，消费者对于此次消费的体验相对更满意。

　　2.雇佣配送员配送。在就餐高峰期，或外卖订单数量很多的情况下，餐饮店中的工作人员已不能有效完成配送任务，商家会招募一些兼职人员负责外卖的配送。这种方式同属于商家自营配送的方式，商家完成备餐的过程，由被雇佣的配送人员完成外卖的配送，雇佣配送员增加了商家外卖服务的成本，但这种方式提高了外卖配送的效率。

　　3.O2O外卖平台配送。“美团外卖”、“饿了么”两大外卖平台都会招聘专职配送人员，并对配送人员进行培训，专职配送人员具有较高的配送效率和专业素质。当点餐者下单后，商家准备完成备餐任务，距离较近的专职配送人员至商家处取餐，再送至消费者手中。在这种配送方式下，商家、配送人员只需各司其职，便能完成整个程序，但遇到问题时需要商家与配送人员及时沟通。

　　二、动态规划法动态规划(dynamic programming)是运筹学中的一个分，动态规划法是用来求解决策过程(decision process)中最优化问题的数学方法。最早出现在二十世纪五十年代初美国的数学家贝尔曼(R.E.Bellman)等一群人所研究的多阶段决策过程(multistep decision process)的优化问题研究中，随着提出了著名的最优化原理，将多阶段的过程转化为一系列单阶段的问题，利用各阶段之间的不同关系，逐个进行求解，创立了一种新的解决这类型过程优化问题的方法——动态规划法。

　　在决策中，通过将大问题分成若干个细小的阶段，然后再将不同的细小阶段通过不同的决策使其每个细小阶段得出最优，然后使整个决策过程达到整体最优。动态规划的基本原理是将一个大问题的最优解转化为求若干子问题的最优解，研究的对象是决策过程的最优化,其变量是变动的状态或流动的时间，最后得到整个系统最优。

　　基本原理一方面给出了一种求解问题的思路，另一方面说明原问题的最优解中包含了子问题的最优解，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，然后每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，这是一种解决最优化问题的算法策略。

　　动态规划求解可分为三个步骤：分解、求解与合并。动态规划的这种原理在管理过程中得到了广泛应用。例如，编制年度计划分为12个阶段，多个项目投资问题可以看做一个项目一个阶段。

　　动态规划数学模型由阶段、策略与决策、状态、指标函数及状态转移方程等5个要素组成，以下是本次研究所需要用到的动态规划数学模型中连和形式的数学模型：

　　fk(sk)=min xk∈Dk(sk){vk(sk，xk)+fk+1(sk+1)，k=1，2，…，k}fn(sn)=0sk+1=T(sk，xk)

　　三、案例分析

　　(一)案例背景

　　本文主要针对在高校的高速生活节奏中，外卖配送最优路线的研究，在这以广州工商学院三水校区为例，广州工商学院创建于一九九五年，随着发展现如今已经发展为本、专科联合的高校，招生人数也是在一年一年的增长，也正是不断的发展，高节奏的校园生活再加上外卖的便捷，衍生了近年来的校园外卖需求的迅速增长，外卖需求在增长的同时显露了许多的问题，如错综复杂校园道路更是为送餐人员带来了不必要的麻烦，再者在学校的高节奏生活中外卖不能准时送达就成了最主要的问题，如何提高送餐的效率，节约成本，让顾客和商家更好地相处，种种的问题都指向了配送能否以最优的路线配送，为了能更好的解决这一问题，以下进行了外卖配送最优路线的研究。

　　(二)案例解剖

　　根据校园的平面图进行了12个主要站点(a1、a2、、、a12)及主要路线的研究，排除其他不必要因素的影响(堵路、施工等)，只考虑畅通情况下的研究，学校平面图如图3-1所示;主要解决的问题是如何规划使外卖从a1区域开始配送到a12区域的路线最短，即求解出a1→a12的最短路线。

　　图3-1 学校平面图

　　三、动态规划法求解

　　(一)求解思路

　　根据动态规划法及案例中的广州工商学院平面图建立模型如图4-1，图中数据来源于实际测量，单位：米。

　　应用动态规划逆序法求解，即根据计算顺序从最后一个阶段开始往前到第一个阶段，通过将完整的阶段过程细分为若干多个细小的阶段之后再进行每个细小阶段问题的最优化求解，即将大问题细分为多个小问题然后再利用每个小问题间的关系逐个解决这些小问题，求解出每个小阶段的最优解，然后达到整体最优解的目的;建立动态规划数学模型如下：

　　fk(sk)=min xk∈Dk(sk){ak(sk，xk)+fk+1(sk+1)，k=1，2，…，k}fn(sn)=0sk+1=T(sk，xk)

　　式子中k表示阶段数;xk表示决策变量;sk表示状态;sk+1表示状态转移方程;fk(sk)表示阶段k状态为sk时到终点a12的最短路程;ak(sk，xk)表示状态为sk选择决策xk时sk到xk的距离;fk+1(sk+1)表示为k+1阶段状态为sk+1到达终点a12的最短路程;Dk(sk)为状态sk的决策集合。图4-1

　　(二)求解过程及结果

　　动态规划逆序法列表求解如下(表中数据统一单位：米)：

　　k=n=6时， f6(a12)=0

　　k=5时，递推方程为：

　　f5(s5)=min x5∈D5(s5){a5(s5，x5)+f6(s6)}

　　f6(s6)到f5(s5)的递推过程如下表4-1

　　表4-1

　　k=4时，递推方程为：

　　f4(s4)=min x4∈D4(s4){a4(s4，x4)+f5(s5)}

　　f5(s5)到f4(s4)的递推过程如下表4-2

　　表4-2

　　k=3时，递推方程为：

　　f3(s3)=min x3∈D3(s3){a3(s3，x3)+f4(s4)}

　　f4(s4)到f3(s3)的递推过程如下表4-3

　　表4-3

　　k=2时，递推方程为：

　　f2(s2)=min x2∈D2(s2){a2(s2，x2)+f3(s3)}

　　f3(s3)到f2(s2)的递推过程如下表4-4

　　表4-4

　　K=1时，递推方程为：

　　f1(s1)=min x1∈D1(s1){a1(s1，x1)+f2(s2)}

　　F2(s2)到f1(s1)的过程只有a1，所以f1(s1)为100+1080=1180，最优决策x1*为a1→a2。

　　综上所述，经过动态规划逆序法列表求解得出从最后一个阶段到第一个阶段计算完成，即已经得出最优解，从a1→a12的最短路长为1180米，综上分析得出最优路线为a1→a2→a4→a6→a9→a12。

　　四、结语

　　本文通过动态规划法为了广州工商学院的外卖配送路线更优进行了研究，在完成最优的配送路线的同时解决了校园高节奏生活外卖配送不及时使得学习、工作效率下降的问题，也为在校园内的外卖配送路线做出更为合理规范化的规划设计。

　　尽管外卖的配送路线可以通过一些人工智能的系统进行规划，但是在高校校园中会受到各种不确定因素的影响(如新增的路障等)从而导致无法真正将系统所规划出来的路线投入使用。本文在规划过程中，在尽可能地排除规划外卖配送路线上的不利因素带来的影响的基础上，通过合理的路线设计、递推计算等最终得出各种可配送路线中最优的外卖配送路线，对实际中外卖配送路线的操作实行具有一定的参考意义，不仅能够为快节奏的校园生活中间接地提高学习工作的效率，还能减少商家在外卖配送上耗费的时间，提高效益。C

　　(作者单位：广州工商学院)

　　参考文献

　　[1]王楠一.O2O电子商务模式下高校外卖配送问题研究.[J].电子商务，2020，(3)：95-96

　　[2]刘竞遥,赵欢欢.多精英协同进化协同进化遗传算法求解外卖送餐路线优化问题.[J].宿州学院学报，2018，33(12)：109-111

　　[3]黄心，吴学群，袁清冽.蚁群算法在外卖配送路径规划中的应用.[J].价值工程，2017，(5)：65-67

　　[4]王荃菲.快餐外卖配送路径方案研究.[D].北京：北京交通大学，2017

　　[5]徐丽媛，段智力，张庆成.最短路线问题的矩阵解法.[J].数学的实践与认识，2018，(12)：178-183