《配送与配送中心》-项目6

任务1单车单点配送的线路优化1.3 相关知识

一、最短路问题的定义在实际送货过程中常常会遇到要从配送中心给单个客户送货的问题,这时企业所期望的通常是能够找到一条从配送中心到客户点最短的运行路线,因为这样能够节省油耗,节省成本。这种需要求从始点到终点的一条路径使得路径总长最短的问题被称为最短路问题。上一页下一页返回任务1单车单点配送的线路优化二、解决方法

1.最大相邻法本方法较简单,思路为从始点或终点开始,找与该点相连的所有点中最近的点,从而得到第二个点,再找与第二个点相连的所有点中最近的点得到第三个点,以此类推。但是注意不能够走回头路,也就是前面找到的点不能够再被找出来一次。以本任务的问题为例解决过程如下:解:如果从始点S点开始,过程如图6-2所示。上一页下一页返回任务1单车单点配送的线路优化可以得到两条路线:S→3→5→t距离9,S→3→2→1→4→t距离10,显然,S→3→5→t为最短路。如果从终点t开始,过程如图6-3所示。显然,两条路线中S→3→2→4→t最短,距离为9。所以,本问题具有两条最短路S→3→5→t和S→3→2→4→t,距离为9,最低运费为450元。上一页下一页返回任务1单车单点配送的线路优化在车辆运行中时常会遇到道路交通管制和单行道的情况,这种情况要看该道路是否处在最短路上,如果处在最短路上会对最短路的方案有影响,否则就不会有影响。如在本任务中如果3→2间的道路交通管制禁止通行,就可以认为3到2的道路不存在,则S→3→2→4→t最短路的方案就不会存在了。如果3→2是单行道,也就是在图中会有3→2的箭头标识,则只能从3→2,不能够从2→3。所以回程时就不能够走t→4→2→3→S这条路线了。

上一页下一页返回任务1单车单点配送的线路优化2.Dijkstra标号法该法是Dijkstra1959年提出的,能求出网络的任一点S到其他各点的最短路。在计算过程中,对每一个点j都要赋予一个标号,这分为固定标号P(j)和临时标号T(j),其含义如下:P(j)———从始点S到j的最短路长;T(j)———从始点S到j的最短路长的上限。一个点j的标号只能是上述两种标号之一。

若为T标号,则需要视情况修改,而一旦成为P标号,就固定不变了。上一页下一页返回任务1单车单点配送的线路优化采用Dijkstra标号法解决过程如图6-4所示。从图中可以看出,该问题有两种可行方案:S→3→2→4→t;S→3→5→t两种方案距离都是9。同时这种方法也求出了S到图中其他各点的最短路和最短距离。到其他各点的最短路如图6-4中箭头所示,最短距离就是在各点旁边的方框中标出的数字。上一页下一页返回任务1单车单点配送的线路优化1.4 技能训练使用电子地图解决单车单点问题。一、实训目的熟悉电子地图的使用方法,能够使用电子地图求两点之间的最短行驶路线。二、实训材料

装有电子地图或能够联网的计算机。

上一页下一页返回任务1单车单点配送的线路优化三、实训步骤

例如,现在有一批商品需要从山东省潍坊市“中百配送中心

运送到最后一份订单“乐福家超市,请找出最短的配送路线。大多数的电子地图都提供了强大的路线选择功能。此处用百度地图来解决这个问题。

(1)打开电子地图并输入网址www.baidu.com,点击地图的位置。(2)输入要查询的城市。网络在线电子地图大多数能够识别IP地址,自动识别你上网地点的所在城市,如果要查询其他城市,可以从查询框输入。上一页下一页返回任务1单车单点配送的线路优化(3)选择驾车,出现地点起始和终止输入框。输入起点和终点,大多数情况下会出现输入地点不准确需要你来做出选择的情况,这时从右侧的选择框中,选择正确的地点,如图6-5右侧圈中所示,从客户档案中可以发现,B点是客户所处地点。(4)输入完成后,“百度一下

得到查询结果,就是相应的最优配送路径,显示在右侧,如图6-6所示。上一页返回任务2单车多点配送的线路优化2.1 任务导入

仍然采用任务1中的网络图,如果要求一辆车从配送中心S出发,装满所有客户需要的货品,给所有客户送完货后再回到配送中心,如何运行可使得总的行驶距离最短?2.2 任务分析

这种送货问题在实际运行中经常会出现,这种配送方法在合理利用车辆吨位、节省运输成本中作用非常大,因此需要掌握这种问题的解决方法。下一页返回任务2单车多点配送的线路优化2.3 相关知识一、TSP问题定义

假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求走的路径路程为所有路径之中的最小值。上一页下一页返回任务2单车多点配送的线路优化二、解决方法

TSP问题的解决方法有多种,大多原理较复杂。此处介绍一种利用软件解决的方法,方法较简单。这种软件就是WinQSB软件。(1)新建问题。运行:程序\WinQSB\NetworkModeling,单击File\NewProblem,出现对话框,问题类型[ProblemType]中选择TravelingSalesmanProblem,输入问题名称TSP1,节点数8,其他默认,单击OK按钮。(2)从菜单EditNodeName,更改节点名称,如图6-7所示。上一页下一页返回任务2单车多点配送的线路优化(3)在出现的对话框中输入所有有连线的两点间的距离。由于该图没有方向所以是双向的,如S:

1距离是10,1:

S距离也同样是10;如果某些道路有方向,则代表该道路是单行道,只能一个方向有距离,如S→1,则只有S颐1是10,1颐S没有距离,如图6-8所示。(4)解决问题。单击求解[SolveandAnalyze],从中选择求解问题[SolvetheProblem],这时会出现如图6-9所示的选择框,这是要求选择解决TSP问题的计算机算法,不同的算法有可能得到不同的结果。上一页下一页返回任务2单车多点配送的线路优化选择每一种算法,记录每一种算法的结果,选择最小的结果。例如,本任务的最小结果就是27,在结果[Results]中选择图解[GraphicSolution],得到图解结果,如图6-10所示,这就是最优行驶路径。2.4 技能训练用电子地图解决单车多点问题。上一页下一页返回任务2单车多点配送的线路优化一、实训任务

使用Google电子地图,从山东潍坊“中百配送中心

发货车一辆,不分先后次序给A福乐多超市、B中百超市、C佳乐家福东店、D乐福家超市四个客户点送货,制订路径最短的车辆运行方案,并写出车辆运行指导手册。

二、实训目的

熟悉google电子地图的使用方法,能够使用google地图解决单车多点问题。三、实训材料

可以上网的电脑。上一页下一页返回任务2单车多点配送的线路优化四、实训步骤

(1)排列所有可能的送货先后次序,给需要送货的客户排序,列出所有的可能性。(2)从配送中心出发按照任务1中的各种可能送货顺序,分别给每一点送货,并回到配送中心。使用google地图设计配送路线,并记录各种送货顺序的路径距离。以ABCD的送货顺序为例,具体操作方法如下:打开google地图网页,单击获取路线,选择图标,打开搜索页面,如图6-11所示。上一页下一页返回任务2单车多点配送的线路优化在输入框中输入各地点。在输入框A中输入起点“山东省潍坊市中百配送中心站,B中输入“福乐多超市,多次单击添加更多目的地4次,输入C“中百超市、D“佳乐家、E“乐福家超市,最后在F中输入起点“山东省潍坊市中百配送中心站。查询路线。单击查询路线,选择某些点的确切地理位置,如图6-12所示。上一页下一页返回任务2单车多点配送的线路优化更改了所有的点的确切地理位置后,将会在右侧出现查询路线方案,在左侧地图框中出现路线图,如图6-13所示。(3)根据上一步记录的各种可能送货顺序的路径距离,选择距离最短的方案,该方案就是路径最短的送货车辆运行路线。(4)根据Google地图对最优方案的描述,写出车辆运行指导手册。

上一页返回任务3多车多点配送的线路优化3.1 任务导入

配送中心A要向B,C,D,E,F,G六个门店配送货物,如图6-14所示,它们之间的距离和每一处的配送货物量见图中标注,配送车辆载重量有2.5吨和4吨两种,请规划总距离最短的配送方案。

3.2 任务分析

解决本问题要求尽量采用数量少的车辆,也就是大车,尽量使得行走的总距离最小。但是本任务中最大车辆载重量为4t,不能装载所有客户的需求量,因此需要多辆车,这样就使得问题从单车多点配送转变成为多车多点配送问题。下一页返回任务3多车多点配送的线路优化3.3 相关知识一、里程节约法的基本原理1.里程节约法的基本规定利用里程节约法确定配送线路的主要出发点是根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案。上一页下一页返回任务3多车多点配送的线路优化下面假设:(1)配送的是同一种或相类似的货物;(2)各用户的位置及需求量已知;(3)配送方案有足够的运输能力。里程节约法制定出的配送方案除了使总的周转量最小外,还应做到:(1)方案能满足所有用户的到货时间要求;(2)不使车辆超载;(3)每辆车每天的总运行时间及里程满足规定的要求。上一页下一页返回任务3多车多点配送的线路优化2.里程节约法的基本思想如图6-15所示,设P0

为配送中心,分别向客户Pi

和Pj

送货。P0到Pi和Pj的距离分别为d

0i和d0j,两个客户Pi和Pj之间的距离为dij,送货方案只有两种即配送中心P0向客户Pi

、Pj

分别送货和配送中心P0

向客户Pi、Pj

同时送货,如图6-15(a)和(b)所示。比较两种配送方案:方案(a)的配送线路为:P0→Pi→P0→Pj→P0,配送距离为:d0=2d0i+2d0j;方案(b)的配送线路为:P0→Pi→Pj→P0,配送距离为:db=d0i+d0j+dij;我们用Sij表示里程节约量,即方案(b)比(a)节约的配送里程:上一页下一页返回任务3多车多点配送的线路优化根据节约法的基本思想,如果一个配送中心P0分别向n个客户Pj(j=1,2,…,n)配送货物,在汽车载重能力允许的前提下,每辆汽车的配送线路中经过的客户个数越多,里程节约量越大,配送线路越合理。

二、解决方法

(1)计算最短距离。根据配送网络中的已知条件,计算配送中心与客户之间及各客户之间的最短距离,结果如表6-1所示。(2)计算节约里程Sij,结果如表6-2所示:(3)将节约里程Sij

进行分类,按从大到小的顺序排序,得到表6-3:上一页下一页返回任务3多车多点配送的线路优化

(4)确定配送线路。从分类表中,按节约里程大小顺序组成线路图。初始方案:对每一客户分别单独派车送货,原路返回,如图6-16所示。配送线路:6条配送距离S0:196km配送车辆:2.5吨×6修正方案1:按节约里程Sij由大到小的顺序,同时考虑车辆额定载重和各点需求量的关系,将E、G连成一条线路,得修正方案1,配送线路1:A-E-G-A,剩余客户点单独配送,配送线路5条,如图6-17

所示。上一页下一页返回任务3多车多点配送的线路优化节约里程:40km配送距离S1:196-40=156(km)由于EG两点需求量之和为2.9t,因此需要1辆4吨车,所以,配送车辆:4吨×1+2.5吨×4修正方案2:在剩余的Sij中,按由大到小的顺序连接F、G,同时考虑车辆额定载重4吨和F点的需求量1.1吨,可以把F点并入线路1,这时需要4吨车1辆,得到配送线路2:A-E-G-F-A,剩余客户点单独配送,配送线路4条,如图6-18所示。

上一页下一页返回任务3多车多点配送的线路优化节约里程:40+39=79(km)配送距离S2:156-39=117(km)配送车辆:4吨×1+2.5吨×3这条线路就是一条有效的配送线路,并且本条线路车辆已经装满,不能够再加入其他客户点了。所以所有与本线路有关联的其他客户点的节约里程都无效了,此处线路EF、DF、CF、DE都无效了,不予考虑。上一页下一页返回任务3多车多点配送的线路优化修正方案3:在剩余可行的Sij中,选择里程节约最大的线路这时找到了CD,考虑C、D两点的需求量之和为1.7吨,这时可以采用一辆2.5吨车完成两点的配送作业,得到配送线路3:A-C-D-A。剩余客户点B单独配送,配送线路3条,如图6-19所示。节约里程:79+14=93(km)配送距离S3:117-14=103(km)配送车辆:4吨×1+2.5吨×2上一页下一页返回任务3多车多点配送的线路优化修正方案4:在剩余可行的Sij中,下一个最大的是BC,也就是BC两点同车配送,这时考虑B的需求量0.8吨,可以考虑将B并入线路3:A-C-D-A,得到线路4:A-B-C-D-A。这时正好需一辆2.5吨的车可以装载B、C、D三家客户的货品,配送线路2条,如图6-20所示。节约里程:93+12=105(km)配送距离S4:103-12=91(km)配送车辆:4吨×1+2.5吨×1所以,最终配送方案为线路1:A-E-G-F-A,线路2:A-B-C-D-A,需要1辆2.5吨车和1辆4吨车。上一页下一页返回任务3多车多点配送的线路优化3.4 技能训练用里程节约法求最优配送方案。一、实训目的掌握使用里程节约法解决多车多点配送问题的方法。

二、实训步