如何合理优化配送资源 ,以最低的成本、最快的速度完成配送[应用知识]

1、连峰商贸有限公司货物配送优化1、公司简介烟台连峰商贸有限公司为个人出资500万建立的胶东地区首屈一指的商贸型企业，占地12000平方米，拥有集办公、仓储、食宿于一体的现代化物流园。公司凭 借规范、科学与人性化的管理制度，得到员工们的一致好评，现已有员工600多人，中层以上管理人员为50人。公司主营业务为蒙牛系列产品2012年底，公司与中粮集团深度合作，投入建成中粮尚品旗舰店，将业务板块由中粮蒙牛拓展为中粮全产业链，包括中粮 旗下长城葡萄酒、进口酒、屯河保健品、中茶、中粮花生、福临门油、米，以及山萃系列山货、安达露西橄榄油等。中粮尚品旗舰店将为消费者提供更多安全、营养、健康的食品。2、问题的提出

2、针对企业现在2012年的合作，使得企业的货物仓储及配送向多元化方向发展，真对现在，一个品牌只有专门车配送，配送车辆的运载量很低，运输路线不固定，资源浪费严重的现象，试图通过合理的优化安排来实现成本的降低。 目前，连峰商贸的货物配送是零售点有需求，就立即补货，车辆的运载量基本都低于50%。并且，在为多个品牌配送的时候，还实行专车配送，没有实现合理的搭配送货，早成了极大的浪费，使得企业的运输成本居高不下。烟台莱山区超市分布图如下：3、城市配送物流发展面临的问题1）城市化进程的加快和交通拥挤问题的加剧，对城市配送提出了更高的要求。一方面，城乡一体化以及城市范围的不断扩大，使得城市配送区域逐渐加大，配

3、送需求量的需求逐渐加大，需要再投入更多的配送车辆来完成配送；另一方面，城市的交通拥堵问题，使配送效率大大降低，而配送企业为提高配送服务质量，满足配送要求，又需要投入配送车辆，配送车辆的再度投入又加剧了交通拥挤。2）供应链管理促使企业对最终一公里配送的重视程度提升供应链管理的实施，使企业更注重交付效率与效果，而大量干线的运输与配载的效率再提升的空间较小，而作为最后一公里的配送由于直接面对客户，直接影响到产品服务与配送时间效率，同时直接关系到企业的市场发展和企业效益，所以重视程度得到很大提高。3）城市配送需求的多样化加大了城市配送公司的难度城市配送由集中的城市配送需求（如超市配送）向集中与分散（如

4、个人）共存的城市配送形式转变，原来工业产品、农业产品、商业配送比例较大，企业配送需求一般配送量大，有比较稳定的需求节拍，可以采用集中配送与固定配送的方法进行配送组织。但是现在由于网上购物、商务活动以及生活需求的多样化等原因，快递以及配送增值服务的需求量不断增加，配送品种多、配送需求量波动大、配送需求点多面广，所以合理化的城市配送组织难度加大。正是由于交通的拥挤，使得我们需要安排好合理的运输路线，不仅是为了节约运输的时间，运输的成本，也是为了有效的规避交通的拥挤，减少因为路线选择问题带来的不必要的损失。基于城市物流配送的特点，配送需求量大，配送品种多，波动性强，配送需求点多的特点，需要将不同的零

5、售点进行合理的归类，按照区块划分，将零售点归入就近的配送点，由就近的配送点进行货物的配送，来减少物流的成本。因此问题的解决就从以上2个方面开始。4、问题的解决如何合理优化配送资源 ,以最低的成本、最快的速度完成配送任务是任何一个现代物流企业的核心目标之一。终端物流企业的配送体系一般如图 1 所示。图中 ,对于终端物流下列条件成立: 客户数量L小于 10; 子仓库数量 M 少于 20; 零售点的数量 N 就很大 ,仅一个大城市区域内部的零售点就可以达到 23 万个; 零售点的需求量 g小于车载量 q。图 1 中,货物的配送是由中心仓库运到子库,再由子库的车辆运到多个零售点(需求点) 。从中心仓库

6、到子库的配送安排可以按运筹学中的一般运输问题解决(因为子库需求量大于车载量) 。文主要关注从子库到零售点配送安排的优化算的实现。记该问题为 P,可描述如下。设子库集合 H = hm ( m = 1, , M) ,对任意 hm 对应一有 k m个元素组成的配送车辆子集Am = am1 , am2 , , amk (子库对应的车辆m意味着该车辆停放在该子库的停车场处) ,对于车辆 amk对应 车载量 qmk ( k =1, , km) 。现有N项货物运输任务(零售点) 构成的集合 V = v1vn ,对于vi 其货物需求量为gimin( qmk(i=1 N;m=1 M;k=1 km ),并且已知每

7、个点(零售点和子库)的实际位置(坐标)及联结各零售点和子库的道路网络图D要求给所有参与配送的车辆下达配送任务书(即确定每一个参与配送的车辆,该运多少货物,沿什么线路,送货到哪几个零售点) ,这样的任务安排能完成所有配送任务并且总费用最小。上述终端物流配送与干线物流配送相比 ,其显著特点是面向需求量很少(与车载量相比)的零售户。正是这一点使得终端物流配送优化问题成了一个非满载的车辆调度问题 ,其实质是一个复的带约束“多旅行商问题”(multi-travelinglesman problem ,MTSP) 。这里的“复杂”体现为 ,每一个子库即是一个 MTSP ,另外该 TSP 应允许路线的局部重

8、复;这里的“带约束”体现为一个车辆的车载量是有限的 ,同时每一个零售点有特定的需求量;这里的“多”体现为每个子库有多辆车(每辆车对应一个旅行商) 。不难证明它是一个非确定性多项式 NP(nondeterministic polynomial)完全问题 ,其求解计算量随着点个数 n 增加而呈指数级增长 ,用穷举搜索法将面临着计算量组合爆炸的困难。只对物流配送中心优化模型(解决的是图 1 中从中心仓库运到子库的优化问题)这个相对简单地问题加以讨论;以前的研究提供了解决物流配送相关的局部问题的算法 ,但都没能针对终端物流配送的特点给出完整实用的算法。本文基于集合分划、启发式贪心策略和边缘交换算法 ,

9、提供针对上述问题一个可行的优化算法(不能保证是最优 ,但较优) 。定义变量 K 为配送车辆总数,则：。定义 wij = minCost ( vi , vj , D) 为点(包括零售点和车辆所在的位置点) vi 和vj之间的最小费用。可以简单的用 vi和vj两点间的最短路径表示,或者在最短路径的基础上考虑其他因素(如道路等级、限速、通行情况和是否有过路费或过桥费等加以修正) ,其中,minCost 为求最小费用函数关于在 GIS中最短路径的求法。公式（2）保证了任意一个零售点只有一辆车送货，公式（3）保证了由一辆车送货的零售点的需求量总和不大于车子的最大运载量。而公式（1）是目标函数，即车辆分配

10、和路线的合理安排保证总费用的最低。问题的分解上述问题看似一个线性规划问题,实则为一个 NP难题。特别是实际应用中 N 很大使得想求得最优解是不可能的。我们的思路是先求一个可行解,然后进行迭代以进一步优化。为简化将问题 P 分解为以下3个问题。1) 车辆分派( P1) :将属于一个子库的零售点在车载量约束条件下分派给所属车辆(即确定车辆负责送货的零售点) 。2) 线路确定( P2) :确定由某一辆车对应送货任务的具体行走线路。3) 迭代优化( P3) :按一定的启发式规则进行分派调整,保证每次调整都比调整前优化。上面P1 、P2实际上得到一个较优的可行解, P3 将其进一步优化。P1问题求解P1

11、是在一个子库内的车辆分派问题。根据集合分划的定义, P1 可以描述为集合 V 的再分划,即对于子集 Vm , 求其一个 Km 分划m =（Vm1 , Vm2 , , Vmk ) 。其中,子集 Vmk对应由车辆amk负责送货,同时 Vmk的需求量总和不大于应的车载量限制qmk 。P1是整个问题的核心,理论上确定了 P1 ,问题的优化程度就确定了。下面以子库 hm 为例说一个可行算法。1）确定子库 hm 大概需要配送车辆数目 km=+1,其中, q 为平均车载量; t为弹性系,取 0.71。2）确定根顾客。这里的根顾客是指首先确定由某车辆送货的零售点,它是该车辆对应分划子集的第一个元素。可以按下面

12、方法确定。选择最远离子库车场的零售点为第一个根顾客,并添加到集合 Vm1中;距离由车场和已确定的根顾客构成的集合最远的零售点作为下一个根顾客,并添加到相应的子集中 ,然后按此规则继续进行,直到选出根顾客数达到所需要的车辆数。3）零售点对根顾客的分派,即确定应由某车辆送货的其他零售点。提出借助于运输问题伏格尔法求初始解的思想求得初始分派的算法,本文提出一种基于最短路径求解结果的贪心策略算法。这里,将每一步都试图达到局部最优的求解方法称为贪心法。由于在求解最短路径时,满足“整体最优则局部也最优”,即一条最短路径中经过的各点到起点的最短路径也在该路上,因而若车场到某一点的最短路径所经历的零售点刚好满

13、足车载量限制,则将这些零售点编为一组由一辆车送货是最优的。正是基于此,设计启发式算法如下。取任意一车辆 amk ,记录其对应根顾客到车场最短路径所经历的零售点集合,记为 V P。若这些零售点集 V P 的总需求量(包括根顾客的需求量)刚好为接近且不大于车载量(原则上,一次出车,车载量应大于70 %) ,则集合V P 就是该车辆对应的子集 Vmk 。若总需求量大于车载量,则尝试着去掉V P 中距车场较近的零售点,直到满足车载量约束为止,将 V P 赋值给 Vmk 。若远小于车载量,另外寻找一个距根顾客最近的且不在 V P中的零售点为准顾客,求准顾客到车场最短路径所经历的零售点集合并添加到集合 V

14、 P 中,重复 过程,直到车载量约束满足VP赋值给Vmk重复 直到所有车辆和所有零售点都分派完毕。P3问题求解安排车辆行走线路的实质是旅行商问题,即给定一个正权完全图 ,求其总长最短的哈密顿回路,它是一个典型的非确定性多项式 NP 完全问题,其求解算法相当复杂。一个多项式时间算法而非指数时间算法是较优的算法。连峰商贸的仓库总部位于芝罘区，因此我们再莱山区看到的他的子仓库的位置。首先我们根据已有信息来标出子仓库的位置。子仓库1的范围是： 子仓库2的范围是：子仓库3的范围是：子仓库1 有25个零售点，子仓库2有26个零售点，子仓库3有19个零售点，小型箱式货车的运载量为2吨，车量的平均运载量一般为70%。零售点的货物需求是随机的，但同一时刻每个零售点所需货物的平均数为10kg根据公式，弹性系数取0.8因此子仓库1需要的车辆数目为3，子仓库2所需的车辆数为3，子仓库3所需的车辆数为2。因此子仓库1设计3条配送路线，子仓库2设计3条配送路线，子仓库3设计2条配送路线。根据算法，