物流配送之车辆优化调度问题.ppt

物流配送之车辆优化调度问题 车辆路径问题 确定路线的原则 效益、成本、路程、吨百公里数、准确性。 安排车辆运行路线和运行时间 8项原则， 扫描法 步骤：将仓库和所有的停留位置画在地图上或坐标上，在仓库位置放一直尺，转动直至交到停留点，判断货量是否超过货车载重或容积，最后对每条路线安排停留点顺序，求距离最小化。 最短路问题 图论方法 一、图的基本概念 图是一个有序对V，E，V是结点集，E是边集； 无向边，与无序结点对(v, u)相关联的边； 有向边，与有序结点对v, u相关联的边； 无向图，每条边都是无向边的图； 有向图，每条边都是有向边的图. 赋权有向图， 给边赋予权值的有向图。 路径求解模型 一、最短路算法模型 给定一个赋权有向图D=(V,A)，对每一个弧 ，相应地有权 ，设 为D中的一条路，即 ，从 到 的所以路中权最小的路 称为从 到 的最短路，即 Dijkstra法 例：如图，路权为时间，在起点A和终点J之间寻求一条运输时间最短的路线。单位：km A到J求解过程 任意点间最短路 矩阵方法 最短路长矩阵： 中间点矩阵(路径矩阵) 例： 小规模路网最短路的Excel求解 最短路问题数学模型： 决策变量 结点i→j弧 是否走(1表示走, 0表示不走) 目标函数 从源点到目的地路最短。 约束条件 1）源点（出发点）净流量为1（表示开始） 2）所有中间点净流量为0（表示有走入必有走出） 3）目的地（终点）净流量为-1（表示结束）。 4） 路径求解模型 例1：如图所示最短路问题 目标函数： minZ=2x12+1x14+3x16 +6x23+10x24+5x25+7x27 +9x35+6x38+5x46+2x47 +3x57+4x58+4x67+8x78 决策变量xij; 约束条件（结点净流量）： V1=1，V8=-1，中间点=0（流出-流入）； Xij0，非负。 解：用Excel路径规划求解 网络中任意两点间最短路的Excel规划求解 例： 无向网络图中任意两点最短路的Excel规划求解 例： 全国公路骨干网最短路的Premium Solver求解 截至2005年底，全国公路总里程达到193.05万公里，路网结构进一步完善。全国公路总里程中，国道132674公里、省道233783公里、县道494276公里、乡道981430公里、专用公路88380公里。特别是“十五”和“十一五”的建设，总规模约3.5万公里的 “五纵七横”国道主干线已基本贯通。这12条主干线全部是二级以上的高等级公路，其中高速公路约占总里程的76%，一级公路约占总里程的4.5%，二级公路占总里程19.5%。它们连接了首都、各省省会、直辖市、经济特区、主要交通枢纽和重要对外开放口岸，覆盖了全国所有人口在100万以上的特大城市和93%的人口在50万以上的大城市，是具有全国性政治、经济、国防意义的重要干线公路。 全国公路骨干网最短路的Premium Solver求解 车辆调度规划（指派问题） 车辆调度规划的Excel求解 案例分析：车辆调度 目标：空驶距离最短 情景一：一对一单程 情景二：一对一往返 情景三：多对一单程 情景四：多对一往返 情景五：多对多单程 情景六：多对多往返 全国43城市的车辆优化调度(Premium Solver求解) Excel自带的Solver工具可以求解200个变量的规划求解问题，对于指派问题，理论上可以求解14×14的指派问题。但对实际的指派问题，可能会复杂很多，可能会有很大失误。 全国43城市的车辆优化调度(Premium Solver求解) 7.6 案例：天通磁心公司运输部的完美转身 天通磁心公司有2个磁芯生产基地，主要向4家生产企业供应磁芯，天通磁心公司原来拥有自己的内部运输队伍，负责向这4家生产企业运输成品磁芯。公司总经理徐总在一次由中国物流与采购联合会组织的物流师培训中，对第三方物流业务印象深刻。徐总完成物流师培训后，回到公司就马不停蹄开展公司的运输业务整合，徐总叫来了公司运输部负责人李总监，并询问公司是否可以引入第三方物流。李总监也承认，现在自己的运输部运作成本偏高，如果可能的话，看看是否可以引入第三方物流，并答应做一下成本核算。李总监对过去一年的运输数据进行了分析，基本得到了比较可靠的产需运作数据(如表7-34所示)。 车辆运输线路选择——图上作业法 宏观调节：物流运输合理化，通过合理选择运输工具、运输方式及线路，组织货物运输，