基于最短路径的外卖配送时间优化问题研究

针对送餐行业顾客的平均等待时间问题，以最短路径原则为基础，建立相应的数学模型。以某地区某天顾客的下单情况为研究对象，运用图论理论将该地区地理简图抽象为无向赋权图，建立顾客等待时间模型，并利用Dijkstra算法得出两区域之间的最短路径，采用随机模拟算法生成动态订单，估计出顾客的平均等待时间。在此基础上，通过改变配送中心选址、增加配送人员数以缩短顾客平均等待时间，达到模型优化的效果。

快节奏的城市生活带来送餐行业的繁荣，很多靠近城市中心的餐馆通宵营业，在接到外卖订单后，将美味的食物交给送餐员——“外卖小哥”，送到顾客手中。由于顾客耐心有限，所以“外卖小哥”需要尽可能快速地到达餐馆取餐并送到顾客所在的地址，否则会被顾客投诉导致被扣工资甚至被解雇的危险。所以如何缩短顾客等待时间成为了外卖配送的中心问题。并且在消费升级趋势下，人们对外卖配送服务的要求也日益增高，这也促使网络外卖平台不断加码以提供更高效的服务体系。要发展现代化、系统化的外卖配送系统，不容忽视的问题就是配送节点和配送线路，然而配送中心选址和配送人员数目又是对配送中心建设规划的重要问题，不仅直接影响到外卖配送的时间，而且还会影响到外卖行业的运营绩效以及未来的发展[1]。因此通过合理选取配送中心的地址，增加配送人员数，缩短顾客平均等待时间，有利于餐馆快速响应顾客需求，提高外卖行业的服务水平以及增强顾客对配送环节的满意度具有重要的现实意义。

由于配送问题在实际生活中广泛存在，目前各国学者对该问题进行了部分研究，但还有许多问题值得商榷。

杨笠涵等[2]以合肥市某知名快递企业配送路径优化问题为研究对象， 分析该企业配送问题， 建立以配送网络成本最小为优化目标的数学模型。范立南等[3]利用遗传算法和TSP 问题的相关理论， 采用改进的自适应遗传蚁群混合算法，对沈阳大学校园内外卖配送路线进行了合理的规划，有效缩短校园外卖配送路径长度，有效提升外卖员的配送效率。黄驰等[4]应用旅行商问题的理论，对外卖配送路径问题进行建模，建立了客户房间之间的距离矩阵，运用遗传算法、MATLAB 编程得出每两个客户房间之间的对短距离、以及送完外卖后回到餐馆的最短路径。翟劲松[5]等在满足顾客需求量和时间窗约束条件下，以配送时间最短为目标，建立了外卖配送路径优化模型，运用遗传算法得出了最优的配送路径。

这样的研究不胜枚举， 但是以配送中心选址和配送人员数目为优化对象的研究还是寥寥无几。

本文将以优化顾客平均等待时间为目标，对外卖配送中心选址问题进行研究。以最短路径原则为基础，建立了相应的数学模型，并运用图论理论将该城区地理简图抽象为无向赋权图，利用Dijkstra 算法得出两城区之间的最短路径，以求解顾客等待时间模型，估计出顾客的平均等待时间，以及给出配送中心选址的最佳方案。与此同时，对该配送中心的配送人员数进行优化，实现两者的共同优化。

2. 顾客平均等待时间模型建立 2.1. 问题描述 以内蒙古大学周边(如下图1 所示)某天的送餐行业顾客下单情况为对象研究其顾客下单规律， 并且基