基于节约里程法结合时间窗约束物流配送线路优化合肥

1、基于节约算法结合时间约束的物流配送线路优化 合肥绿和农业生鲜品配送线路的优化 汤月 物流工程 目录 背景及绿和农业概况01 合肥绿和农业生鲜品配送线路 存在的问题 02 VRP优化策略03结论与展望04 背景及绿和农业概况1 1.1 背景 近年来随着物流业的快速发展，物流企业为了能够在激烈的市场竞争中保 持优势地位，都在想方设法降低物流配送成本，提高自身竞争力。如何规 划配送路线，减少不必要的人员、时间和金钱的浪费，使运输成本降到最 低是一个有待解决的科学问题，而基于各种算法研究车辆路径规划问题( Vehicle Routing Problem)是目前比较常见的思路。 当前，效率低下的生鲜物流已成为阻止我国果蔬商品生产和流通产业化发 展的瓶颈。为突破这一瓶颈，研究生鲜物资的物流配送问题已迫在眉睫。 配送车辆路径问题是一个NP-hard问题。 1.2 绿和农业概况 安徽绿和农业科技有限公司坐落在安徽省最大的农产品批发市场周 谷堆农产品批发市场旁。公司专业从事蔬菜种植、禽畜养殖和为酒店、工 厂、学校、企事业单位、政府机关食堂、生鲜超市等进行新鲜蔬菜、水 果、肉类、粮油等农副产品一站式配送服

2、务。 绿和农业将以特有的新鲜、安全、快速、高效的优势，合理的价格， 取得广大企业用户的青睐。在我们的服务领域，我们的专业程度、技术服 务水平、卫生监督、产品质量以及先进的服务理念已经得到客户的充分认 可，从而保障我们与客户保持长期友好的合作关系。 宗旨：公司的宗旨是第一时间产地直供、减少中间环节，为客户创造价值。 我们替您买菜，当天配送，我们只做蔬菜的搬运工。让消费者买菜不用再去 菜市场挑挑拣拣，只要在家做等“收菜”即可。让消费者足不出户就能品尝 到新鲜、健康、营养的蔬菜。 配送优势：农产品物流是以农业产出物为对象,通过农产品产后加工、包装、 储存、运输和配送等物流环节,做到农产品保值增值,最终送到消费者手中。 由于农产品本身特 质,以及产销地域广阔分散的特点，对农产品物流规划、 方式和手段提出了比较高的要求,这个物流过程是目前农产品实现市场价值的 关键环节。作为现代物流的新业态，农产品物流统一组织货源,进行检验检 疫、整理清洗、分检包装,根据定单要求直接送到消费者手中，完成农产品从 “田间”到“餐桌”的全程服务，具有安全、高效、便利的特点。 合肥绿和农业生鲜品配送路线存在的问题 2

3、2.1 生鲜品配送线路现状 生鲜配送线路缺乏规划，效率较低 合肥绿和农业生鲜配送几十家门店，本着追求高效配送效率和最低配送成本的原 则出发，以合肥政务区大区为配送区块作业，每日凌晨按照前一日超市的销售反 馈，装配好生鲜品，在凌晨5:00-8:00时段内送到各门店。各门店分布在合肥政务 区城市的角角落落，主要都围绕一些居民区而建，路况复杂多变。 绿和农业配送中心安排车辆送货时，考虑了车辆载货的核定重量以及门店分布得 区域，因此常由一辆车辆负责某一区域的门店生鲜配送。门店配送的先后由配送 中心事先制订好，但是其制定的方法是以配送中心出发后最近的门店开始配送， 而后配送距离上一家最近的门店，直至最后配送完一家门店返回配送中心。因冷 藏车的送货路线合理性有限，冷藏车到达门店后，很容易与其他送货车辆发生冲 突，互相干扰货物进出路径和搬运优先次序等。这样的局面常常造成冷藏车用较 长时间滞留在一家门店等待卸货的情况，既浪费宝贵的生鲜货物配送时间，又极 大的浪费了运输设备的效能。部分司机为了和其他送货车辆争抢卸货时间，甚至 还提前将生鲜品卸货至门店货仓门口，等待门店工作人员收货，造成生鲜品长时 间暴露

4、在外，大大降低了生鲜品的品质。 2.2 现有的配送方案分析 由于合肥绿和农业旗下的门店有很多，本文选取位于合肥政务区市天鹅湖的 10家门店进行研究。 合肥政务区市天鹅湖绿和农业生鲜品配送中心与门店之间的距离 门店P0天鹅湖店怀宁路店东流路店翡翠路店聚云路店南二环路店高河西路店潜山路店休宁路店祁门路店 P00106811710117811 天鹅湖店100824866662 怀宁路店680612410124412 东流路店826084610648 翡翠路店11412808241082 聚云路店784480810448 南二环路店1061062806844 高河西路店1161210410601082 潜山路店76461048100210 休宁路店86448448208 祁门路店11212828421080 合肥政务区市天鹅湖绿和农业门店的货物需求量及时间窗 按当前合肥政务区华润配送规划的原则，即以最为靠近配送中心的门店开始送货，以下门店距离一 门店最近来进行下一门店的送货，直至送完为止回到配送中心，这10家店目前的配送情况如下: 配送路线为:P。配送中心怀宁路店聚云路店潜山路店休宁路店一东流

5、路店天鹅湖店 南二环路店翡翠路店祁门路店一一高河西路店P。配送中心 配送里程:6+4+4+2+4+2+6+2+2+2+11=45公里 从配送里程来看，配送路线规划总体比较短，但是由于路线规划时没有考虑到门店的时窗要求， 因此车辆到达门店时往往需要等待比较长的时间才能卸货，因此车辆在门店的停留的时间平均长达 26分钟。由于配送时间的增加，还导致制冷成本随之上升。所以需要一定的路线优化使总成本达到 最低。 门店翡翠路店怀宁路店东流路店潜山路店聚云路店南二环路店高河西路店休宁路店天鹅湖店祁门路店 需求量（吨）0.080.10.120.050.080.150.060.050.10.02 门店要求的时 间 5：45-6:306:10-7:005:45-6:156:50-7:505:40-6:357:25-8:006:30-7:107:15-8:005:20-5:406:40-7:20 门店可接受的 时间 5:40-6:456:00-7:005:30-6:156:40-7:505:30-6:357：10-8：106:30-7:107:00-8:005:00-5:406:35-7：30 VRP优化策

6、略 3 3.1 VRP 求解的方法 综合过去有关车辆路线问题的求解方法，可以分为精确算法(exact algorithm)与启发式解法(heuristics) (1)精确算法 精确算法一般会随着问题规模的增大而呈现数据量增大的情况，计算成本 比较大，因此很难有效解决大规模的VRP问题，实际应用范围有限。 （2)启发式算法 由于VRP是NP-hard问题，这类问题的大型实例很难以用精确算发求解，多 年来很多专家对此类车辆运输问题进行了研究，提出了各种各样的启发式方 法。启发式算法包括构造算法蚁群算法遗传算法节约里程法 节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。设 为配送中心，分别向用户a和b送货。我们用a和b之间的距离为lab，送货方案 只有两种即配送中心向用户a, b分别送货和配送。比较两种配送方案: 方案1:配送路线为 ，配送距离为 方案2:配送路线 ，配送距离为 我们用 表示节约里程数，即方案2比法案1节约的配送里程: 根据节约法的基本思想，如果一个配送中心P。分别向m个客户配送货物，在 汽车载重能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多， 里程

7、节约量越大，配送线路越合理。 节约里程法运算速度较快，特别是在小规模的配送路径优化问题中，节约里 程法的优化解与最优解更加接近，其在实际应用中也能得到较满意的结果， 合肥绿和农业对超市配送规模较小，所以本文将以节约里程法对绿和农业配 送车辆路径进行优化。 3.2有时间窗约束的VRP 时间约束问题大体分为两种，一种是“允许延时”的“软时间窗”问题，一 种是“不允许延时”的“硬时间窗”问题。 在建立惩罚成本模型时，设门店a可接受的时间窗Ma , Na ，门店要求的时 间窗ma, na。根据配送车辆到达门店的时间，可以分三种情况: 配送车辆在门店要求的时间之前到达。（在Ma，ma)内到达，在Ma之前到达 ） 配送车辆在门店要求的时间内到达（在ma, na内到达，无惩罚成本） 配送车辆在门店要求的时间后到达（在(na,Na内到达，在Na之后到达） 综上所述，惩罚函数可以表示为 式中Xa是生鲜品送达门店的时间; a和是惩罚系数; P(Xa)是惩罚成本; P是生鲜单位价值; qb是每个门店生鲜需求量。 3.3绿和农业生鲜品配送中心车辆路径优化方案 3.3.1车辆路径问题模型建立 (1)模型建立的约

8、束条件 门店的数量固定且位置己知; 门店的生鲜品需求量一定; 生鲜品送达时间窗一定; 每辆车的行驶时间不得超过司机工作的时间; 每家门店且只能由一辆车一次性完成送货; 每条配送线路各门店的需求量之和不得超过车辆的最大核载量。 车辆由配送中心出发，有序到达各门店后返回配送中心。 (2)软时间窗约束下的模型建立 运输成本 生鲜品的制冷成本 综上所述，我们构建的生鲜品配送车辆路径问题的目标函数： 利用节约里程法结合时间窗约束，我们将带有时间窗约束的合肥绿和农业VRP 求解步骤归纳如下: 第一步，将门店按时间窗先后顺序排序; 第二步，计算配送中心到各门店的节约里程数; 第三步，从配送中心发车，首先将时间窗要求最早的门店作为第一个配 送对象，然后将节约总成本最大的门店加入路线，成为第二个配送对象; 第四步，重复第三步，直至所有的门店都被排入路线内。 带有时间窗约束的合肥绿和农业VRP具体求解过程如下: 第一，根据门店要求的时间进行先后排序 第二，利用式 计算各门店间的节约里程数。 天鹅湖店怀宁路店东流路店翡翠路店聚云路店南二环路店高河西店潜山路店休宁路店祁门路店 需求量（吨）0.10.080.1

9、20.080.10.060.020.050.050.15 门店要求的时 间 5:20-5:405:40-6:355:45-6：155:45-6:306:10-7:006:30-7:106:40-7:206:50-7:507:15-8:007:25-8:00 门店可接受的 时间 5:00-5:405:30-6:355:30-6:155:40-6:456：00-7:006:30-7:106:35-7:306:40-7:507:00-8:007:10-8:10 合肥政务区市天鹅湖绿和农业门店间的节约里程数 门店天鹅湖店怀宁路店东流路店翡翠路店聚云路店南二环路店高河西路店潜山路店休宁路店祁门路店 天鹅湖店0 8161791415111219 怀宁路店80859657105 东流路店1680111112991211 翡翠路店17511010191881120 聚云路店991110098101110 南二环路店1461219901591417 高河西路店155918815081120 潜山路店1179810980138 休宁路店1210121111141113011 祁门路店19511201017208110 第三，由于天鹅湖路店要求的时间最早，因此以天鹅湖路店作为第一个配送 点，配送车辆到达的时间为5:30，接下来的门店选择 最终的配送路线为Po配送中心天鹅湖路店东流路店一休宁路店聚云路 店怀宁路店高河西路店祁门路店南二环路店一-翡翠路店潜山路店 -P。配送中心 配送里程:8+4+2+8+4+12+2+4+2+10+7=63公里 配送时间:63公里40公里/小时+10分钟10603.2小时 运输成本:63公里0.7元/公里=44.1元 制冷成本:3.2小时12元/小时+202.5元/吨0.81=55.7元 惩罚成本:0 配送总成本:44.1+55.7=99.8元 按照优化前的路线计算的话 配送时间:45公里40公里/小时+26分钟1060=5.5小时 运输成本:45公里0.7元/公里=31.5元

《基于节约里程法结合时间窗约束物流配送线路优化合肥》由会员ji****en分享，可在线阅读，更多相关《基于节约里程法结合时间窗约束物流配送线路优化合肥》请在金锄头文库上搜索。