陆路运输问题新.doc

第 10 章 陆路运输 在公路和铁路运输以及第 11 章中将要研究的航空运输中，都存在很多优化问题。 这陆路运输网络与航空运输网络之间的主要区别在于陆路运输的网络更为密集，参与 者更多。边境的开放和运输商之间的强烈的竞争都使得优化方法成为降低运输成本从 而能够从竞争中胜出得关键因素。 第 10.1 节将给出一个车辆租赁问题，在其中为保持理想的车队大小，需要将汽 车在各个租赁代理处之间转运，并需要使费用最小。在 10.2 节中描述了一个在不同 运输方式之间进行分配的问题：需要将给定量的货物从网络中的一个结点运输到另一 个结点，在此网络中存在多种运输方式，每种方式的成本和运输能力均已知。第 10.3 节将处理一个战略层次的经典问题，即如何为仓库选址才能够最小化开办仓库和向客 户运输的成本。在 10.4 节中，我们将解决一个最优化燃油运输路径的问题。在第 10.5 节中描述了一个多种运输方式组合（联合运输）的问题，此问题与 10.2 节中的问题 的不同之处在于更换运输方式时也会带来一定费用支出。本章的最后一节中将研究一 个如何对整个车队进行规划的问题。 10.1 汽车租赁 有一家小型汽车租赁公司，此公司有 94 辆可供出租的汽车，分布于 10 个代理 点中。每个代理点的位置都将以地理坐标 X 和 Y 的形式给出，单位为千米。我们假 定两个代理点之间的距离约为它们之间欧氏距离（即最短距离）的 1.3 倍。下表给出 了各个代理点的位置坐标，以及第二天早晨汽车租赁的需求量和前一天晚上各个代理 点拥有的汽车数。 表格 10.1：车辆租赁代理点信息 代理点12345678919X 坐标0201830353355112Y 坐标02010120252710015汽车需求量10681197157912当前拥有量813481221411157 假定汽车转运的成本为每辆车每千米 0.50 欧元，请找出如何在各个代理点之间 调度分配汽车才能够满足各处的需求，并且使转???成本最低。 10.1.1 模型的数学表达 对于代理点集合 AGENTS 中的每个代理点 a 我们都用 X a 和 Ya 表示其地理坐 标。 REQa 表示在代理点 a 处汽车的需求量， STOCK a 为此代理点当前的汽车保有 量。这两个值之间的差值即表示此处汽车数富余（如果为正数值），或者不足量（负 值 ）。此问题即找出车辆富余的代理点集合 EXCESS 和车辆不足的代理点集合 NEED 之间的最小费用车辆流。由于总富余量等于总不足量，因此必定存在能够满 足各处需求的车辆流。首先，我们定义变量 moveab 表示在两个代理点之间的车辆流： ?a ∈ EXCESS ,b ∈ NEED : moveab ∈ N （10.1.1）  每个车辆富余的代理点都需要将其富余的车辆发送到别处（10.1.2），每个车辆 不足的代理点都需要从别处接受到数量等于不足数量的车辆（10.1.3）。 ?a ∈ EXCESS : ?b ∈ NEED : ∑ moveab = STOCK a ? REQa b∈NEED ∑ moveab = REQb ? STOCK b （10.1.2） （10.1.3） a∈EXCESS 目标函数即最小化总转运成本（10.1.4），其中 COST 表示每辆车每转运 1 千米 的成本， DISTab 表示在两个代理点 a 和 b 之间的距离。 minimize ∑ ∑COST ? DISTab ? moveab a∈EXCESS b∈NEED （10.1.4）  最小费用流问题是一个运输问题（transportation problem），其特征在于都有一 组来源的，拥有数量有限的资源，以及一组需要此资源的目的地。对于最小费用流问 题，通常可以采用单纯形算法求解线性规划从而找到整数解。因此约束条件（10.1.1） 可以用简单的非负约束条件取代。 10.1.2 模型实现 上述数学模型可以实现为下面的 Mosel 程序。在读入数据之后，我们首先检查 当前汽车的总保有量是否等于汽车的需求量，如果不相等，则停止此程序。如果相等， 则分别找出车辆富余和车辆不足的代理点集合。在下面声明决策变量数组和距离矩阵 时将用到这两个集合。 model E-1 Car rental uses mmxprs declarations AGENTS = 1..10 ! 汽车租赁代理点 REQ: array(AGENTS) of integer ! 汽车需求数量 STOCK: array(AGENTS) of integer ! 当前汽车保有量