线路规划与成本控制

1、唐龙政 主要内容 预备知识 运输优化与成本控制基本理论 第一节 物流运输服务选择决策 第二节 货物运输调配决策 第三节 物流运输线路的优化 第四节 行车路线及时刻表的制订 第五节 运输工具与货载的最优分配 2 预备知识 一、物流运输组织、规划的基本原理 二、物流运输的质量 三、物流运输的合理化 3 （一）规模经济（economy of scale） 思考：规模经济存在的原因？ 有关的固定费用可以按整批货物的质量分摊。 4 （二）距离经济（economy of distance） 指每单位距离的运输成本随距离的增加而减少。距 离越长，固定费用分摊后的值越小，使得每单位距 离支付的费用越小。 距离

2、经济的合理性类似于规模经济，尤其体现在运 输装卸费用上的分摊。 5 （一）货运质量事故分类 1、重大事故：货损金额在3000元以上的运输质量事故，以 及经省级有关部门鉴定为珍贵、尖端、保密物品在运输过程 中发生灭失、损坏的事故。 2、大事故：货损金额在500-3000元的货运质量事故。 3、一般事故：货损金额在50-500元的货运质量事故。 4、小事故：货损金额在20-50元的货运质量事故。 货损金额在20元以下的货运质量事故，不作为事故统计上 报，但企业要作为内部记录和处理。 6 物流运输的质量 （二）货运质量事故考核指标 6 6 1010 完成货运周转量完成货运周转量 货运质量事故次数货运

3、质量事故次数 货运质量事故频率货运质量事故频率 7 物流运输的质量 （二）货运质量事故考核指标 100% 货运总吨数 货损吨数 货损率 100% 货运总吨数 货差吨数 货差率 8 物流运输的质量 （二）货运质量事故考核指标 100%100% 货运总收入金额货运总收入金额 质量事故赔偿金额质量事故赔偿金额 货运质量事故赔偿率货运质量事故赔偿率 100%100% 完成总货运量吨数完成总货运量吨数 的货运量吨数的货运量吨数按托运要求的时间完成按托运要求的时间完成 完成运量及时率完成运量及时率 9 物流运输的合理化 10 （一）合理运输的概念 （二）不合理运输的表现形式 （三）运输合理化的措施 物流运

4、输的合理化 （一）合理运输的概念 合理运输（Reasonable Transportation）： 11 物流运输的合理化 （二）不合理运输的表现形式 12 对流运输 迂回运输 重复运输 倒流运输 过远运输 运力选择不当 无效运输 表现形式 13 甲乙丙丁 对流运输 1、对流运输 是指同类的或可以互相代替的货物的相向运输，它是不合理运输最突出、最普遍的一 种。主要有两种表现形式： （1）明显对流 （2）是隐蔽对流 派生形式：倒流运输，即同一批货物或同批中的一部分货物，由发运站至目的站后， 又从目的站往发运站方向运输 表现形式 14 迂回运输 迂回运输 不经过最短路径的绕道运输，“近路不走走远路

5、”。 表现形式 15 甲 乙丙 3、重复运输-出现不必要的中转 指同一批货物由产地运抵目的地，没经任何加工和必要的作业，也不是为联运及 中转需要，又重新装运到别处的现象。 重复运输是因物流仓库设置不当或计划不周使其在中途卸下，导致增加运输环节、 浪费运输设备和装卸搬运能力，延长运输时间的不合理运输方式。 表现形式 16 甲乙 丙 4、倒流运输 指同一批货物或同一批中的部分货物，由始发站运往目的站，又从目的站往始发 站方向运输。 表现形式 17 过远运输 5、过远运输 指凡是可以从附近取得所需物资的供应而不去就近组织，相反却从相反的地方运 来，从而造成不必要的浪费，即在相同条件下舍近求远的物品运

6、输方式。 未考虑各种运输工具的经济技术特点而进行不适当的选 择造成的不合理。常见的有以下几种形式： （1）违反水陆分工使用，弃水走陆的运输。 （2）铁路短途运输。 （3）水运的过近运输。 18 7、运力选择不当 三、物流运输的合理化 （三）运输合理化的措施 19 第一节:物流运输服务选择决策 20 一、物流运输方式选择的原则 （一）安全性原则 （二）及时性原则 （三）准确性原则 （四）经济性原则 21 二、基于物流总成本比较的运输方式选择 22 【例7-1】某公司欲将产品从位置A的工厂运往位置B的公司 自有仓库，年运量D=700000件，年存货成本为产品价格的 30%。公司希望选择使总成本最小

7、的运输方式。据估计，运 输时间每减少一天，平均库存成本可以减少1%。各种运输服 务方式的有关参数见表7-1。 二、基于物流总成本比较的运输方式选择 【例7-1】基于运输成本与库存成本的总成本分析方法： 23 成本类型成本类型计算公式计算公式铁路运输铁路运输驮背运输驮背运输公路运输公路运输航空运输航空运输 运输成本运输成本R D70 000105 000140 000980 000 在途库存在途库存ICDT/365362 466241 64486 30134 521 工厂存货工厂存货ICQ/2900 000418 500378 000182 250 仓库存货仓库存货I(C+R)Q/2903 00

8、0420 593380 520190 755 总成本总成本 2 235 4661 185 737984 8211387526 三、承运人的选择与评价 24 三、承运人的选择与评价 假设一共有N个评价指标。对于某备选承运商来说，客户可通 过统计分析、专家打分或其他信息获取途径，得出该承运商的 N个指标（取值）得分情况，分别用X1、X2，.Xn表示。 则，该承运商的综合得分为： 25 专注专业、持续改善专注专业、持续改善 26 表7-3 承运商评估报告示例 最高分评价标准 承运人 分数 备注 13满足接货时间表13 13满足搬运10 9运输时间9 10运输时间一致性7 7费率5 3附加费1高的住宅

9、搬运 5运营比率396.5增长 4收益性3 3索赔频率3 3索赔解决3 10账单错误7 9跟踪能力7 11设备可用性l无平台装货卡车 100总分72 第二节 货物运输调配决策 一、多起讫点间的直达运输 二、存在中间转运的物资调配 三、图上作业法 27 表上作业法 一、多起讫点间的直达运输 对于多点间直达运输问题，描述如下： 28 a 1 a2 am b1 b2 bn Cij Xij 供供 应应 地地 需需 求求 地地 图7-1 多点之间的物资运输调拨问题示意图 一、多起讫点间的直达运输 销地销地 产地产地 B1B2Bn产量 A A1 1 x x11 11 x x12 12 x x1n 1n a

10、 a1 1 A A2 2 x x21 21 x x22 22 x x2n 2n a a2 2 A Am m x xm1 m1 x xm2 m2 x xmn mn a am m 销量销量 b b1 1b b2 2 b bn n 29 一、多起讫点间的直达运输 （一）产销平衡的运输问题（ai= bj） 1产销平衡运输问题数学模型 30 一、多起讫点间的直达运输 （二）运输问题数学模型的特点 31 专注专业、持续改善专注专业、持续改善 32 一、多起讫点间的直达运输 专注专业、持续改善专注专业、持续改善 33 min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x1

11、1+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0 (i=1,2；j=1,2,3） 一、多起讫点间的直达运输 （二）运输问题数学模型的特点 专注专业、持续改善专注专业、持续改善 34 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 一、多起讫点间的直达运输 （二）运输问题数学模型的特点 专注专业、持续改善专注专业、持续改善 35 模型系数矩阵特征 一、多起讫点间的直达运输 （二）运输问题数学

12、模型的特点 、 西北角法 最小元素法 沃格尔法（vogel） 2、解的最优性检验（判断是否为最优调运方案） 闭回路法 位势法（对偶变量法） 3、解的改进 4、重复2、3两步，经有限次调整，得到最优解。 36 一、多起讫点间的直达运输 （三）用表上作业发求解运输问题的基本步骤 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 37 4124 3 11 102 85 11 9 6 1、确定初始基本可行解西北角法 88 64 814 （三）用表上作业发求解运输

13、问题的基本步骤 一、多起讫点间的直达运输 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 38 4124 3 11 102 85 11 9 6 1、西北角法得到的初始调运方案为： 88 64 814 总运输费用为：372（怎么计算？） （三）用表上作业发求解运输问题的基本步骤 一、多起讫点间的直达运输 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销

14、量 8 814141212141448 39 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 40 1、确定初始基本可行解沃格尔（Vogel）法 （三）用表上作业发求解运输问题的基本步骤 一、多起讫点间的直达运输 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 行罚 数 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 列罚数 销地销地 产地产地 B B1 1

15、B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 42 43 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 2、解的最优性检验闭回路法 44 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 11 12 2 1616 A A2 21 1- 1- 1 1010 A A3 310101212 2222 销量销量

16、8 814141212141448 检验数计算结果 （三）用表上作业发求解运输问题的基本步骤 一、多起讫点间的直达运输 2、解的最优性检验位势(对偶变量)法 45 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量ui A A1 1 1616 u1 A A2 2 1010 u2 A A3 3 2222 u3 销量销量 8 814141212141448 vjv1v2v3v4 （三）用表上作业发求解运输问题的基本步骤 一、多起讫点间的直达运输 2、解的最优性检验位势(对偶变量)法 46 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量ui A A1

17、1 1616 u1( ) A A2 2 1010 u2( ) A A3 3 2222 u3 销量销量 8 81414121214144848 vjv1 ( )v2 ( )v3 ( )v4 () （三）用表上作业发求解运输问题的基本步骤 一、多起讫点间的直达运输 47 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 1616 A A2 2 1010 A A3 3 2222 销量销量 8 814141212141448 练习：求解如下运输问题 48 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 8 8 A A2 2

18、5 5 A A3 3 5 5 销量销量 4 43 35 56 6 要求：用三种方法求出初始方案，用两种方法对最小元素法得 到的初始方案进行检验，如果初始方案不是最优，请调整到最 优。 1总产量大于总销量： 则增加一个假想的销地Bn+1，其销量为： 2总销量大于总产量： 则增加一个假想的产地Am+1，其产量为： 49 n j j m i in bab 11 1 m i i n j jm aba 11 1 n j j m i i ba 11 m i i n j j ab 11 （四）产销不平衡问题 一、多起迄点间的直达运输 50 销地销地 产地产地 B1B2BnBn+1(贮存)产量 A A1 1

19、x x11 11 x x12 12 x x1n 1n x x1.n+1 1.n+1 a a1 1 A A2 2 x x21 21 x x22 22 x x2n 2n x x2.n+1 2.n+1 a a2 2 A Am m x xm1 m1 x xm2 m2 x xmn mn x xm.n+1 m.n+1 a am m 销量销量 b b1 1b b2 2b b3 3b bn n a ai i- - b bj j （四）产销不平衡问题 一、多起迄点间的直达运输 二、存在中间转运的物资调配 51 t1 t2 tm b1 b2 bn Ckij Xkij 供应地供应地 需求地需求地 a1 af 中转站

20、中转站 二、存在中间转运的物资调配 目标函数为： 约束条件为： （1）配送量生产能力的限制： k=1，2，f； （2）流通中心发送能力的限制： i1，2，m； （3）满足零售店需求量： j=1，2，n； （4）变量非负： 52 m i n j kijkij f k XCZ 111 min n j kkij m i aX 11 n j ikij f k tX 11 f k jkij m i bX 11 0 kij X （二）数学模型 二、存在中间转运的物资调配 例7-2某公司生产变压器，一个工厂在A市，每天生产能力为 150 ，另一个工厂在B市，每天生产能力为200 。需求点C市和 D市的需求量

21、均为130。公司还需要两中间转运站E市和F市进行 整合运输。各点间运输单位费用见表7-4。试确定从工厂到需求 点的最优路线。 53 二、存在中间转运的物资调配 （三）求解方法 1、将运输模型转为简单的运输问题 （1）增加一虚拟的行或列来平衡需求 （2）构造一个包括所有城市（起点、终点和中间点）作为供 需点的运输表（包括虚拟列）。 （3）根据表7-5的规则，得到最终运输表 转运问题中转运问题中 点的性质点的性质 在运输表中的在运输表中的 供应值供应值 在运输表中的在运输表中的 需求值需求值 供应点供应点起始供应起始供应+总供应总供应总供应总供应 转运点转运点总供应总供应总供应总供应 需求点需求点

22、总供应总供应起始需求起始需求+总供应总供应 空空 点点0起始供应起始需求起始供应起始需求 54 需求和供应量确定准则需求和供应量确定准则 专注专业、持续改善专注专业、持续改善 55 表7-6 最终运输表 二、存在中间转运的物资调配 （三）求解方法 专注专业、持续改善专注专业、持续改善 56 表7-7 初始调运方案 二、存在中间转运的物资调配 （三）求解方法 三、图上作业法 57 （一）图上作业法要解决的问题 回顾一下什么是对流运输？ 58 20 303020 2 43 (20) (20) (30)(30) 这是对流这是对流 20 303020 2 43 (20) (20) (30)(30)(1

23、0) 什么又是迂回运输呢？ 59 2 0 6 0 4 0 4 0 2 4 6 3 (20) (20) (40) 圈长：圈上每一条边的长度之和（记为 l）l =15 先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。 内圈长 l内=8 外圈长 l外=4 是最优解 码？ 8, 2 l l 内 不是最优的. 称为迂回运输 调整方案：对内圈各流量中最小调运量，进行反向调运 (40) (20) (20) 准则：内外圈长都小于圈长的一半的无对流的调运方案 为最优方案 67. 22 ll ll 外内 此时为最优调运方案 三、图上作业法 1、交通图的符号 发点用“ ”表示，并将发货量记在里面，收点用

24、“ ”表 示，并将收货量记在里面。两点间交通线的长度记在交通线 旁边。 2、调运物资的流向图 物资调运的方向（流向）用“ ”表示，并把 “ ” 按调运方向画在交通线的右边，把调运物资的数量 记在“ ”的右边并加上括号。 在交通图成圈时，若运输方向沿逆时针方向，则需将流向 “ ”画在圈外，称为外圈流向，反之，若运输方向沿顺 时针方向，则需将流向“ ”画在圈内，称为内圈流向， 60 （二）交通图 三、图上作业法 1、交通图不含圈 没有对流运输即是最优方案。 61 （三）基本步骤 三、图上作业法 62 5 2 3 7 8 1 35 A1 A2 B1 A3 B2 B3A4B4 (5) (7) (1)

25、(2) (1) (5) (2) （三）基本步骤 三、图上作业法 63 （三）基本步骤 三、图上作业法 64 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 5 57 73 3 A A2 2 3 32 23 3 A A3 3 4 44 43 31 1 销量销量 2 23 31 11 17 （三）基本步骤 三、图上作业法 65 3 1 3 1 1 3 2 A1 A2 B1 A3 B2 B3 B4 7 5 3 4 4 4 3 2 (3) (1) (2) (1) (1) （三）基本步骤（三）基本步骤 三、图上作业法 66 3 1 3 1 1 3 2 A1 A2

26、B1 A3 B2 B3 B4 7 5 3 4 4 4 3 2 (3) (1) (1) (1) (1) (2) (2) (1) （三）基本步骤 三、图上作业法 销地销地 产地产地 B B1 1B B2 2B B3 3B B4 4产量 A A1 1 2 21 13 3 A A2 2 2 21 13 3 A A3 3 1 11 1 销量销量 2 23 31 11 17 67 最优调运方案 （三）基本步骤 三、图上作业法 练习： 68 20 30 A 30 50 20 70 100 20 60 30 B C D E F G H I 23 45 23 25 18 13 (20) (10) (50) (2

27、0) (80) (60) (20) (30) （三）基本步骤 三、图上作业法 练习： 69 20 30 A 30 50 20 70 100 20 60 30 B C D E F G H I 23 45 23 25 18 13 (20) (10) (50) (20) (80) (60) (20) (30) (30) (40) (20) （三）基本步骤 2、交通图含圈 第三节 物流运输线路的优化 一、起迄点不同的单一路线优化 二、起迄点重合的单一路线优化 70 一、起迄点不同的单一路线优化 71 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 5 4 1 5 8 4 6 4 2 4 6

28、 9 7 5 1 2 4 2 （一）动态规划法（逆序递推） 72 一、起迄点不同的单一路线优化 n=4n=3n=2n=1 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 5 4 1 5 8 4 6 4 2 4 6 9 7 5 1 2 4 2 （二）标号法（Dijkstra方法） 例7-3 73 O A B C D E T 22 5 4 1 7 4 4 3 1 7 5 起点 终点 O A B C D E T 22 5 4 1 7 4 4 3 1 7 5 起点 终点 图7-5 运输网络图 一、起迄点不同的单一路线优化 表7-8 Dijkstra算法步骤表 74 二、起迄点重合的单一路线

29、优化 （一）旅行商问题（TSP）模型 1、问题描述 75 C A B D 38 18 31 22 27 45 444241 242221 141211 . . . . xxx xxx xxx Xs 0382745 3801831 2718022 4531220 ij C n i n j ijij XCZ 11 min 专注专业、持续改善专注专业、持续改善76 二、起迄点重合的单一路线优化 （一）旅行商问题（TSP）模型 2、解决办法 枚举、分支定界、现代优化方法（遗传算法等）启发式算法。 贪婪算法： 选择距离出发点最近的顾客位置； 再从剩下的位置中选距离已选择的位置最近的顾客位置。 如果所有位

30、置都被选择了，则停止，否则返回。 C A B D 38 18 31 22 27 45 专注专业、持续改善专注专业、持续改善 77 （二）中国邮递员问题 预备知识：图论的相关概念 “顶点”表示某对象节点（设施地点或企业单位）。 “边”表示对象之间的某种特性（如距离）。 边上的非负数字称为“权”。 以V为顶点的边的数目称为顶点V的“次”。 次为奇数的点，称为奇点；次为偶数的点，称为偶点。 由点、边交替构成的序列称为“链”；起点与终点相同的链就 称为“圈”。 二、起迄点重合的单一路线优化 专注专业、持续改善专注专业、持续改善 78 （二）中国邮递员问题 预备知识：图论的相关概念 二、起迄点重合的单一

31、路线优化 （二）中国邮递员问题 1确定可行方案（如果有奇点存在 ） 79 V2 V9 5 9 4 3 4 2 4 5 6 4 3 V4 V8 V6 4 V5 V3 V1 V7 V3 V1 V2 V4 4 V5 V6 V7 V8 V9 二、起迄点重合的单一路线优化 图图7-8 街道图街道图 图图7-9 加重复边后的街道图（可行方案）加重复边后的街道图（可行方案） 专注专业、持续改善专注专业、持续改善 80 （二）中国邮递员问题 2判断最优方案（两条标准） V2 V3 V4 4 V9 3 5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V4 4 V9 3

32、5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V4 V9 3 5 5 4 6 9 2 3 4 4 4 4 V7 V6 V5 V8 V1 （a）调整方案一）调整方案一 （b）调整方案二）调整方案二 （c）调整方案三（最佳方案）调整方案三（最佳方案） 第四节 行车路线及时刻表的制定 81 一、运输路线及时刻表制订的原则 1同一车辆服务的客户按距离聚类 82 仓 库 仓 库 2避免行车路线交叉 3尽可能使用大载重量车辆，减少出车数量 4取货/送货混合安排 5从距仓库最远的站点开始设计线路 83 图7-13 合理与不合理的行车线路 一、运输路线及时刻表制订的

33、原则 二、行车路线制订的扫描法 1、基本原理 先以仓库(物流中心)为原点，将所有需求点的极坐标算出， 然后依角度大小以逆时针或顺时针方向扫描，若满足车辆 装载量即划分为一群，将所有点扫描完毕后在每个群内用 最短路径法求出车辆最佳行驶路径。 2、基本步骤 第一步：求出各客户点的极坐标。 第二步：扫描划分客户群。 第三步：确定每辆车的最佳路径（TSP算法 ）。 84 专注专业、持续改善专注专业、持续改善 85 二、行车路线制订的扫描法 【例7-4】某运输公司为其客户企业提供取货服务，货物运回 仓库集中后，将以更大的批量进行长途运输。所有取货任务均 由载重量为10吨的货车完成。现在有13家客户有取货

34、要求， 各客户的去货量、客户的地理位置坐标见表7-10。运输公司 仓库的坐标为（19.50，5.56）。要求合理安排车辆，并确定 各车辆行驶路线，使总运输里程最短。 86 3 2 2.4 2.8 3.1 1.8 2.5 2.25 2.6 2.1 1.5 1.9 1.6 1#线路 2#线路 3#线路 11 12 9 10 7 8 2 1 5 4 3 13 6 0 二、行车路线制订的扫描法 三、行车路线制订的节约法 基本思想：如果将运输问题中的两个回路合并成一个回路， 就可缩短线路总里程（即节约了距离），并减少了一辆卡 车。 87 COA CBO A B O 仓库 A B O 仓库 （a）初始路线

35、 总里程= COA + CAO + COB + CBO CAO COB （b）将两个站点合并成同一线路 总里程= COA + CAB + CBO CAB COA CBO 图7-15 节约法的图形描述 专注专业、持续改善专注专业、持续改善 88 【例7-5】某配送中心要为13个客户提供配送服务，配送 中心的位置、客户的坐标及客户的订单规模见表7-11。配 送中心共有4辆卡车，每辆车的载重量是200件。 由于送货成本与车辆行驶总里程之间密切相关，公司经理 希望获得总行驶距离最短的方案。如何分配客户？如何确 定车辆行驶路径？ 三、行车路线制订的节约法 89 三、行车路线制订的节约法 1确定距离方阵

36、90 22 )()( BABAAB yyxxC 三、行车路线制订的节约法 2计算节约矩阵 91 三、行车路线制订的节约法 3将客户划归到不同的运输路线 92 三、行车路线制订的节约法 93 三、行车路线制订的节约法 94 三、行车路线制订的节约法 95 11 7 8 9 10 12 13 5 2 3 4 6 1 0 X Y 三、行车路线制订的节约法 第五节 运输工具与货载的最优分配 一、航线配船优化问题 二、多车多品种货载配车优化 96 一、航线配船优化问题 （一）问题概述 设船公司经营n条航线。第j条航线上规划期正向货运量预 测为Qj，公司拥有装载能力分别为Ni的m种船型；i型船的 船舶艘数

37、为mi，一艘i型船在j航线上规划期可以完成的最 大往返航次数为nij；一艘i型船在j航线上完成一个往返航 次所花费的全部成本为kij。要求将这些船合理地安排在这 几条航线上，使公司的经济效益最好。 97 专注专业、持续改善专注专业、持续改善 98 一、航线配船优化问题 （二）数学模型的建立 1参数说明 I 船型编号，i=1,2，m； J 航线编号，j=1,2，n； Xij i型船在j航线上每季度完成的往返航次数，是决策变 量； Yj j航线上未被船舶承运的货物量，也是决策变量； Kij 每艘i型船在j航线上完成一个往返航次所花费的运营 成本； j航线上单位货物未被承运产生的费用损失； 每艘i型

38、船在j航线上每季度可以完成的最大往返航次 数； i型船的集装箱装载能力； i型船的船舶数量； j航线的正向运量。 j ij n i N i m j Q 专注专业、持续改善专注专业、持续改善 99 一、航线配船优化问题 （二）数学模型的建立 2目标函数 3约束条件 j n j jij m i n j ij yxKk 111 min 0, 0 1 1 1 jij jjij m i i iij n jij yx QyxN mx n 专注专业、持续改善专注专业、持续改善 100 一、航线配船优化问题 （三）航线配船优化举例 【例7-6】假设某船公司拥有3种吨位的集装箱船舶共30搜， 分别是1500TE

39、U的8艘、850TEU的12艘、500TEU的10艘。 现开辟班轮航线6条，各航线季度集装箱运输量、船舶在 每条航线每季度最多能完成的航次数、每艘船在各航线每 往返航次的成本（万元）以及每条航线发现的机会成本 （万元/TEU）如表7-17至表7-19所示。求不同航线的船 舶最佳配置方案。 一、航线配船优化问题 （三）航线配船优化举例 101 102 一、航线配船优化问题 （三）航线配船优化举例 专注专业、持续改善专注专业、持续改善 103 解：（1）目标函数： 一、航线配船优化问题 3323132 3222121312111 5 .202528125. 0 20242515. 0182430m

40、in xxxy xxxyxxxK 24143 24251 . 0 xxy 26165352515434 283215. 02030351 . 05 .18xxyxxxyx 636 125. 032yx 专注专业、持续改善专注专业、持续改善 104 解：（2）约束条件： 一、航线配船优化问题 且均为整数, 0, 0, 70005008501500 30005008501500 45005008501500 50005008501500 80005008501500 60005008501500 10 2 1 5 1 4 1 4 1 4 1 12 3 1 2 1 4 1 3 1 4 1 3 1 8

41、 2 1 3 1 2 1 3 1 2 1 613611 6362616 5352515 4342414 3332313 2322212 1312111 363534333231 262524232221 161514131211 yyxx yxxx yxxx yxxx yxxx yxxx yxxx xxxxxx xxxxxx xxxxxx 专注专业、持续改善专注专业、持续改善 105 解：（3）求解结果 一、航线配船优化问题 二、多车多品种货载配车优化 （一）问题描述 已知有m辆零担作业车，其载重量和容积分别为G1， G2，Gm和V1，V2，Vm。现有n批货物H1， H2，Hn，其重量和体积分别为g1，g