小翠副食超市对水窑沟住宅楼配送路径优化问题研究

经济管理学院《运输与配送》结课论文题目小翠副食超市对水窑沟住宅楼配送路径优化问题研究小翠副食超市对水窑沟住宅楼配送路径优化问题研究摘要：现在互联网技术已经渗入到各行各业，随着互联网的不断发展，近几年电商行业发展越来越好。特别是在疫情封控的影响下，人们足不出户，也能在短时间能购买到一定的生活物资。物流配送作为物流过程中的重要环节，其成本占物流总成本的很大一部分，配送成本的增加必然会导致物流总成本的上升。综上所述，只有对配送路径的各方面进行优化，才能提高配送效率，降低成本，保证配送安全，增加收益。目前，用于解决路径优化模型的算法主要有扫描算法、遗传算法、模蚁群算法等。每种算法都有其较为合适的使用场合。其中，启发式算法能够快速求解路径规划问题，且结果更加接近最优解。本文以水窑沟住宅楼为例，在软时间窗条件下，采用节约算法对小翠副食超市配送物流路径进行求解和分析，实现配送路径的优化和成本的降低。关键词：路径优化；节约算法；软时间窗相关理论基础1.1时间窗约束带时间窗的车辆路径问题（VehicleRoutingProblemwithTimeWindows，VRPTW）目前研究较为广泛，是一种基础的带有能力约束的车辆路径问题，实际的配送场景中，客户对车辆的配送有被访问时间的要求，客户是否在配送时间上得到满足影响了客户对整体配送服务的满意度。在对此类问题进行求解时，配送车辆不仅要考虑客户点空间距离的影响，同时要将客户的时间窗考虑进去，通过车辆路径的合理规划，达到诸如成本最低、客户满意度最高等优化目标。按照时间窗约束的不同标准可以分为以下三种类型：（1）硬时间窗硬时间窗是指客户的时间窗为硬性要求，货物仅在客户要求的时间窗内配送才会被接收，若车辆提前到达，则需要等待；若车辆推迟到达，则客户拒绝接收货物。货物在客户时间窗内送达，惩罚值为0，在时间窗外送达，会产生一个非常大的正值M，硬时间窗下的惩罚函数图像如下图所示：（2）软时间窗软时间窗中客户对时间的要求相对宽松，货物在客户时间窗外送达也可以被接收，但是由于违反了时间窗要求，会产生一定形式的惩罚，惩罚的程度由违反的时间长短来决定，以处罚替代等待或拒收更符合实际情况。货物在客户时间窗内送达，不会产生惩罚；提前和延迟送达均会产生惩罚，且惩罚程度一般不同，通常情况下函数呈线性，软时间窗下的惩罚函数图像如下图所示：（3）混合时间窗混合时间窗是指客户对货物配送时间的要求同时具有软、硬两种时间窗的部分特点，车辆在客户时间窗内配送，则惩罚值为0；早于或晚于时间窗送达，会产生与违反时间长短相关的惩罚值，而当早于某个时刻或晚于某个时刻送达，会产生非常大的惩罚值，且取值一般不同，混合时间窗下的惩罚函数图像如下图所示：1.2车辆路径问题的求解算法车辆路径问题一直广受学术界关注，关于VRP求解算法的研究非常丰富，总的来看，可以分成精确算法和近似算法两大类，而近似算法又可以分为构造启发式算法、改进启发式算法和智能启发式算法三种，其中构造启发式算法一般与改进启发式算法结合使用，用在构造初始解阶段，二者可以统称为经典启发式算法。几种具有代表性的算法如下图所示：1.3节约算法节约算法（C-W算法）在1960年由Clarke和Wright提出，其求解思想是，将配送中心分别与所有客户点相连，形成与客户点数目相同的配送线路条数，计算总距离或总成本；然后计算将两个客户点相连产生的费用节约值，直至不再产生节约值时停止，在满足车载量、时间窗等约束下，节约值大的两个客户点会被优先排列，该算法具有易于调整、效果理想等特点。2模型构建2.1问题描述小翠副食超市是位于水窑沟住宅楼内的以经营生活用品、瓜果蔬菜为主的小型超市，在疫情的影响下，为防止大家出现聚集情况，小翠副食超市推出网上点单，送货上门的服务。在订单确定的基础上，如何安排送货路线成为需要解决的问题。大家对于收到货物的时间没有具体要求，只是希望越快越好。水窑沟住宅楼实况地图如下： 2.2模型建立水窑沟住宅楼共包含九栋居民住宅楼，根据地图及实地考察，建立水窑沟住宅楼与小翠副食超市的距离矩阵，如下图所示：2.3模型分析2.3.1计算节约里程表根据已知距离矩阵，通过EXCEL建立节约里程表并计算出九栋居民住宅楼九个确定地点中任何两个地点的节约里程数，如下表所示：2.3.2对节约里程进行排序参考已经计算出的节约里程表，将两两地点间的节约里程数按降序进行排列，如下表所示：2.3.3确定配送路线在上边的计算过程中，我们已经计算出小翠副食超市与水窑沟住宅楼九栋居民住宅楼的距离矩阵，并根据距离矩阵计算出相应的节约里程表，然后将两两地点间的节约里程数按降序进行排列。根据排序后的节约里程表，我们可以确定任意几个地点的配送路线。比如在当天小翠副食超市同时收到了1号楼、2号楼、8号楼、9号楼的订单，根据节约里程表可以确定配送路线为“小翠副食超市-2号楼-1号楼-8号楼-9号楼”，根据计算，优化后的配送路线可以为小翠小翠副食超市节约560米的配送距离。3总结本文中将C-W节约算法用于小翠副食超市对水窑沟住宅楼配送路径优化问题中，成功实现了总距离减少，总成本降低。而且，节约算法操作简单，使用起来比较方便，适用于需求点较少的配送问题。但是，启发式算法本身具有无