✓路线选择问题的基本类型
起迄点不同的单一路径规划 多个起迄点的路径规划 起点和终点相同的路径规划
❖ 起迄点不同的单一路径规划
✓单一路径规划问题
单一路径规划问题是已知一个由链和节点组成的 网络，其中节点代表由链链接的点，链代表节点 之间的成本（距离、时间或距离和时间的加权平 均)，求始点到终点的最小成本。
✓起迄点问题的求解方法
对于“流动推销员”问题，可以用计算机进行求 解。
例子：小型配送问题
有一个以某仓库为基地，包括四个经停 靠站点的小型配送问题，仓库、四个站 点之间的运行时间如下图所示。
每年运输批次
10 20 20 40
在采购成本和运输时间的变化忽略不计的情 况下,如何选择使运输成本最小的运输方式?
卡利奥箱包公司对运输方式的评估计算表
成本类型 计算方法 铁路运输 驮背运输 卡车运输 航空运输
运输成本 在途库存
RD
(0.10)(700000 (0.15)(700000 (0.20)(700000 (1.40)(700000
17×20 ＋12×60 ＋17×10＝2090。
例2有转运点的运输问题
腾飞电子仪器公司在大连和广州有两个分厂生 产同一种仪器，大连分厂每月生产450台,广州 分厂每月生产600台。该公司在上海和天津有 两个销售公司负责对南京、济南、南昌、青岛 四个城市的仪器供应。另外因为大连距离青岛 较近，公司同意大连分厂向青岛直接供货，运 输费用如下图，单位是百元。问应该如何调运 仪器，可使总运输费用最低？
600 12
3
3 21 450 4
2
3
6 63
4
4
4 6
5
5 200 6 150 7 350 8 300
如图：1—广州、2—大连、3—上海、4—天津 5—南京、6—济南、7—南昌、8—青岛
解：设Xij为从i地到j地的运量，则可以建立线性 规划模型如下：
Minz=2X13+3X14+3X23+X24+4X28+2X35+6X36+3X37+6 X38+4X45+4X46+6X47+5X48
✓单一路径规划问题的求解方法
最短路径法（Shortest Route Method）
例子：阿马里洛与沃思堡之间行车最短路线
德克萨思州德阿马里洛和沃思堡之间的高速公 路网示意图如下，节点之间的每条链上都标有 相应的行车时间，节点代表公路的连接处。
问：如何找到阿马里洛与沃思堡之间行车时间 最短的路线？
s.t. X13+X14≤600（广州分厂供应量限制）
X23+X24+X28 ≤ 450（大连分厂供应量限制） X35+X36+X37+X38－X13 － X23=0(上海销售公司) X45+X46+X47+X48－X14－ X24=0(天津销售公司) X35+X45=200 X36+X46=150 X37+X47=350 X38+X48+X28=300 Xij≥0,其中i=1,2,3,4;j=1,2,3,4,5,6,7,8。
30
D
300
95 60
235
60
需求量 70
80
50
200
最小周转量为：40×50＋30×125 ＋20×80 ＋ 60×95 ＋20×60 ＋30×45＝15600（吨公里）。
❖ 起迄点重合的问题
✓起迄点重合问题的界定
起迄点重合的问题主要指车辆必须返回起点行程 才结束，如从某仓库送货到零售点然后返回的路 线（从中央陪送中心送到食品店或药店），如从 零售店到客户本地配送的路线设计（商店送货上 门）；校车、送报车、垃圾收集车和送餐车等的 路线设计。
据估计，运输时间从目前的21天每减少一天， 平均库存水平可以减少1％。每年西海岸仓库 卖出D＝700000件箱包。公司可以利用以下 运输服务：
运输服务方式
铁路运输 驮背运输 卡车运输 航空运输
运输费率（美 元/单位）
0.10 0.15 0.20 0.40
门到门运输时 间（天）
21 14 5 2
✓单一路径规划问题的求解方法
运输问题的表上作业法
例1产销平衡的运输问题
现有三个生产地A、B、C供应某种商品；四个 销售地1、2、3、4，各自供应量和需求量如 下表所示，试求出最佳调运方案？
费用
1
A 15
B 20
C 25
需求量 30
2
18 14 12
60
3
19 15 17
20
4
13 17 22
X21+X22+X23+X24=30 X31+X32+X33+X34=70 X11+X21+X31=30 X12+X22+X32=60 X13+X23+X33=20 X14+X24+X34=40 Xij≥0,其中i=1,2,3;j=1,2,3,4。
用WINQSB求解，可以得到最优解如下表所示：
❖ 基本的成本权衡
✓ 最佳服务方案
如果不将运输服务作为竞争手段，那么能够使该运输服务 的成本与该运输服务水平导致的相关间接库存成本之间达 到平衡的运输服务就是最佳服务方案。
✓ 运输速度、可靠性与库存水平
运输的速度和可靠性会影响托运人和买方的库存水平（订 货库存和安全库存）以及他们之间的在途库存水平，速度 慢、可靠性差的运输服务必将导致物流渠道中更多的库存。
第一步：列出商品产销平衡表
费用
a
b
c 供应量
A
40
B
70
C
30
D
60
需求量 70 80 50 200
第二步：列出交通示意图
70 50 40 75 70 80 80 95 60
60 50
45 30 表示两地距离 表示接收点，其中数字表示接收量 表示发运点，其中数字表示发运量
第三步：列出以距离为单位费用的运输 问题产销平衡表
供应商A正在考虑如果将铁路运输方式改 为航空或卡车运输，是否可以获得更多的 收益？
各种运输方式下每箱配件的运输费率和平 均运送时间已知如下：
运输方式 铁路运输 卡车运输 航空运输
运输费率（美 元/箱）
运送时间（天）
2.50
7
6.00
4
10.35
2
不同运输方式下供应商A的利润对比
运输方 式
)=70000
)=105000 )=140000 )=980000
(0.30)(30)(70 (0.30)(30)(70 (0.30)(30)(70
ICDT/365
(0.30)(30)(70 0000)(14)/3650000)(5)/365=0000)(2)/365=
0000)(21)/365 =241644
费用
1
A 15 30
B 20
C 25
需求量 30
2
18 14
ቤተ መጻሕፍቲ ባይዱ12 60
60
3
19
15 10 17 10
20
4
13 20 17 20
22
40
供应量 50 30 70 150
即有X11=30, X14=20, X23=10, X24=20, X32=60, X33=10，其余的Xij=0;
最小总运费z*=15×30＋13×20 ＋15×10 ＋
40
供应量 50 30 70 150
解：设Xij为从第i个产地到第j个销售地的 运量，则可以建立线性规划模型如下：
Minz=15X11+18X12+19X13+13X14+20X21+14X2 2+15X23+17X24+25X31+12X32+17X33+22X34
s.t. X11+X12+X13+X14=50
✓ 如果分拨渠道中有多个供应商可供选择，运输服务 的选择会成为供应商和买方的联合决策
供应商通过选择运输方式来争取买方的订单，理智的买方 则会通过更多的购买来回应供应商的选择
例子：匹兹堡制造商的供应商选择
位于匹兹堡的一家设备制造商需要从两个供应 商那里购买3000箱塑料配件，每箱配件的价格 是100美元。目前，从两个供应商采购的数量 是一样的。两个供应商都采用铁路运输，平均 运输时间也相同。但如果其中一个供应商能够 将平均交付时间缩短，那么每缩短一天，制造 商将会将采购订单的5％（即150箱）转给这个 供应商。如果不考虑运输成本，供应商每卖出 一箱配件可以获得20％的利润。
90分钟
2
1 138
66
84
5
120
84 9
132
3
90 6
60 8
126
348
126
153
132
48
10
4 48
7
150
1 阿马里洛
10 沃思堡
9 俄克拉荷马城
用WINQSB求解，得到最短路线为:
1
2
5
9
10 最短时间为384分钟
❖ 多起迄点的问题
✓多起迄点问题
如果多个货源地服务多个目的地，要指定各目的 地的供货地，同时要找到供货地、目的地之间的 最佳路径，该类问题常发生于多个供应商、工厂 或仓库服务于多个客户的情况下。
❖ 考虑竞争因素
✓ 合适的运输方式有利于创造有竞争力的服务优势
如果供应渠道中的买方从多个供应商那里购买商品，那么 物流服务就会和价格一样影响买方对供应商的选择