文档介绍：配送管理与实务
项目6 配送线路优化
单车单点配送的线路优化
多车多点配送的线路优化
单车多点配送的线路优化
教学目标
知识目标:
;
;
3. 掌握里程节约法安排车辆路径的方法;
技能目标:
能够根据不同的情况安排车辆的运行最优路径;
配送线路优化
配送中心S向客户t配送货物,各点之间的路径距离公里数如线上的数据所示,请制定最优配送运行方案。
单车单点配送的线路优化
任务1
◆任务描述:
◆相关知识:
最短路问题(单车单点配送)
单车单点配送解决方法
单车单点配送的线路优化
任务1
最短路问题一般描述如下:在一个网络图中,给定一个始点和一个终点,求始点到终点的一条路径,使得路径总长最短。
除配送路径选取问题外,许多实际的问题都可以归纳总结为最短路径问题,例如:两地之间的管道铺设、线路安装、道路修筑等
最短路问题
◆解决方法:
最大相邻法
Dijkstra(迪杰斯特拉)标号法
单车单点配送的线路优化
任务1
WinQSB
电子地图
最大相邻法
任务1
思路:从始点或终点开始,找与该点相连中所有点中最近的点,从而得到第二个点;再找与第二个点相连的最近的点,得到第三个点,以此类推。
注意:不能够走回头路,也就是前面找到的点,不能够再被找出来以此。
最大相邻法
任务1
解:如果从始点S点开始,过程如下图所示:
如果从终点t开始,过程如下图所示:
最大相邻法
任务1