陆路运输问题.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 REQabNEED moveab = REQb STOCK b（10.1.2）（10.1.3）aEXCESS目标函数即最小化总转运成本（10.1.4），其中 COST 表示每辆车每转运 1 千米的成本， DISTab 表示在两个代理点 a 和 b 之间的距离。minimizeCOST DISTab moveabaEXCESS bNEED（10.1.4）最小费用流问题是一个运输问题（transportation problem），其特征在于都有一组来源的，拥有数量有限的资源，以及一组需要此资源的目的地。对于最小费用流问 题，通常可以采用单纯形算法求解线性规划从而找到整数解。因此约束条件（10.1.1） 可以用简单的非负约束条件取代。10.1.2 模型实现上述数学模型可以实现为下面的 Mosel 程序。在读入数据之后，我们首先检查 当前汽车的总保有量是否等于汽车的需求量，如果不相等，则停止此程序。如果相等， 则分别找出车辆富余和车辆不足的代理点集合。在下面声明决策变量数组和距离矩阵 时将用到这两个集合。model E-1 Car rental uses mmxprsdeclarationsAGENTS = 1.10 ! 汽车租赁代理点REQ: array(AGENTS) of integer! 汽车需求数量STOCK: array(AGENTS) of integer! 当前汽车保有量X,Y: array(AGENTS) of integer! 租赁代理点位置坐标 COST: real! 转运一辆汽车每千米成本 NEED: set of integer! 汽车数不足的代理点 EXCESS: set of integer! 汽车数富余的代理点end-declarationsinitializations from e1carrent.dat REQ STOCK X Y COSTend-initializationsif sum(a in AGENTS) (STOCK(a)-REQ(a) 0 then writeln(Problem is infeasible)exit(0)end-if! 计算出汽车数富余和汽车数不足的代理点集合forall(a in AGENTS)if STOCK(a) -REQ(a) 0 thenEXCESS += aend-iffinalize(NEED); finalize(EXCESS)declarationsDIST: array(EXCESS,NEED) of real! 代理点之间的距离move: array(EXCESS,NEED) of mpvar! 代理点之间的汽车转运情况end-declarations! 计算代理点之间的距离forall(a in EXCESS,b in NEED)DIST(a,b):= 1.3*sqrt(X(a)-X(b)2 + (Y(a)-Y(b)2)! 目标函数：总转运成本Cost:= sum(a in EXCESS,b in NEED) COST*DIST(a,b)*move(a,b)! 汽车数富余的代理点forall(a in EXCESS) sum(b in NEED) move(a,b) = STOCK(a) -REQ(a)! 汽车数不足的代理点forall(b in NEED) sum(a in EXCESS) move(a,b) = REQ(b) -STOCK(b)forall(a in EXCESS,b in NEED) move(a,b) is_integer! 求解此问题minimize(Cost)end-model在这个模型实现中我们使用了指数运算符。注意，我们也可以用 r0.5 来表示r ，这与使用预定义的 Mosel 函数 sqrt（r）是相同的。10.1.3 结果优化器将计算出最低总转运成本为 152.64 欧元。下表列出了达到此最低成本时 在代理点之间转运汽车的具体方案，此方案能够得到我们所需的最终汽车分布。表格 10.2：车辆转运的最优方案-1346710富余量20105107500300038000004492300016不足量24351510.2 选择运输方式 在法国西南部有一家公司，这家公司需要将 180 吨存放于仓库 D1 到 D4 中的化学产品运输到 3 个回收中心 C1，C2 和 C3。仓库 D1 到 D4 分别储存有 50，40，35， 和 65 吨化学产品，总计为 190 吨。可以选用两种运输方式：公路运输和铁路运输。 仓库 D1 只能通过公路向回收中心 C1 和 C2 进行运输，运费分别为 12 欧元/吨和 14 欧元/吨。仓库 D2 只能向回收中心 C2 运输，可以选择通过铁路或公路，运费分别为12 欧元/吨和 14 欧元/吨。仓库 D3 可以通过公路向回收中心 C2 运输（9 欧元/吨）， 或通过铁路或公路向回收中心 C3 运输，运费分别为 4 欧元/吨和 5 欧元/吨。仓库 D4 可以通过铁路或公路向回收中心 C2 运输，运费分别为 11 欧元/吨和 14 欧元/吨，或 者通过铁路或公路向回收中心 C3 运输，运费分别为 10 欧元/吨和 14 欧元/吨。此公司与铁路公司签订的化学物品运输合同规定，每次运输量至少应为 10 吨， 最多为 50 吨。除了标准的安全规章之外，对公路运输不存在其他特殊的限制。那么 此公司应如何运输这 180 吨化学物品才能够使总运费最低？10.2.1 模型的数学表达我们将把此问题建模为一个具有固定总通过量的最小费用流问题（minimum cost flow problem）。我们先来构造一幅图 G = (NODES , ARCS )。首先向结点集合NODES 中加入一组结点，代表各个仓库，然后再加入一组结点，代表回收中心（参 照图 10.1）。弧集合 ARCS 中包含了在所有仓库和回收中心之间可能存在的连接。运输方案即对应于图 G 中的一个流，即在每一条弧 (i , j )上的流 flowij 。弧 (i , j )具有一个最小通过量 MINCAPij（除铁路运输其他均为 0），一个最大通过量 MAXCAPij（即 运力上限，除铁路运输外均为无穷大），以及每吨的运输成本 COSTij 。从一个仓库到一个处理中心之间的两种运输方式需对应两条不同的弧。在这样的图中，两个结点之间至多有 p 条弧，称为 p -图。这样的图无法编码为（二维）矩阵： 例如费用矩阵中的元素 COSTij 只能表示一个费用。为将此图转化为两个结点之间至多有一条弧的图，可以为仓库 i 和处理中心 j 之间的每种运输方式都创建一个假想的结点。例如，在仓库 D2（结点 3）和处理中心 C1（结点 12）之间存在一条公路连 接和一条铁路连接。为避免生成具有两条弧 (3,12)的 2-图，我们可以创建一个结点 6对应于铁路运输，以及一个结点 7 对应于公路运输。则铁路运输即变为路径 (3,6,12) ， 公路运输即变为 (3,7,12)。只为弧 (3,6)和 (3,7) 设置通过量和费用。图 10.1：运输网络图在此图中未将仓库的存储量纳入考虑。为此，我们创建一个源结点（假想的结点1），此结点将用弧 (1,d ) 连接到每个仓库结点 d 上，且此弧的通过量为 MAXCAP1d ， 对应于仓库 d 处的存储量。因此离开仓库 d 的流不会超过此值。为方便数学模型的表达，我们也创建一个宿结点（假想的结点 15），并且连接到每个处理中心结点上。 这样最终得 到的图即可 以表示为图 10.1，其 中 每条弧 (i , j ) 都对应于一个三 元 组(MINCAP ,MAXCAP ,COST)。“-”表示通过量为无穷大。ijijij在此数学模型中包含了流守恒约束条件（10.2.2），也称为 Kirchhoff 定理：每个结点处的入流都等于此结点处的出流（除了源和宿结点之外）。每条弧上的流都至少取值为 MINCAPij （约束条件（10.2.3），且不超过最大通过量 MAXCAPij （约束条 件（10.2.4）。式（10.2.5）对总流量加以约束，即 MINQ = 180 吨。这样就迫使离开源（结点 1）的流总量等于 MINQ 。由于在此网络中流保持守恒，因此也可以使 用宿结点的入流总量等于 MINQ 作为约束条件。在这个约束条件中，我们可以将等号替换为 号，由于在最小化总成本时也将最小化总流量，因此此时总运输量将取此 下界值。最后要解释一下目标函数（10.2.1）。 COSTij 是每吨的运费成本，因此通过弧 (i , j )运输的流 flowij 的费用为 COSTij flowij 。因此最小化总运费即最小化所有弧 上的总费用。最终，通过定义这样的图，我们可以得到相当简洁的数学模型。注意，在约束条 件（10.2.3）中也隐含给出了变量非负的约束条件。minimizeCOSTij flowij(i , j )ARCS（10.2.1）i NODES ,i SOURCE ,SINK : flow ji =(i , j )ARCS flowij(i , j )ARCS（10.2.2）(i , j ) ARCS :(i , j ) ARCS :flowij MINCAPijflowij MAXCAPij（10.2.3）（10.2.4） flowSOURCE ,i(SOURCE ,i )ARCS= MINQ（10.2.5）除了这种基于图的问题数学表达之外，也可以将使用方式 m 从仓库 d 运输到目 标 c 的运量表示为决策变量 trasnport dcm ，对每个可能出现的三元组 (d ,c,m)都建立 这样的决策变量，从而得到另一种问题表达方式。这样总运量就可以表示为所有有定义的变量 trasnport dcm 的和，目标函 数即所有可 行的三元组 (d ,c,m) 对应的 COSTdcm trasnport dcm 的和。每种运输方式的最小和最大运力限制将表示为对应变 量 trasnport dcm 的上界和下界约束条件，这一点与上述的（10.2.3）和（10.2.4）很相似。对于我们这个问题，这种表达方式可能比基于图的模型表达要容易一些。但在后面的模型实现和进一步的讨论中，我们仍然使用这种更一般的最小费用流模型，即（10.2.1）到（10.2.5）给出的模型。10.2.2 模型实现从这个问题可以引出一个经典的问题，即图的编码。可以将图定义为 N N 的 矩阵形式，其中 N 为结点总数，并为每对由弧相连的结点 (i , j )都定义一个流变量。 然而，对于稀疏图，如我们所使用的这个图，更常用（效率也更高）的方法是将图表示为弧的列表的形式。在下面的 Mosel 程序实现种就使用了这种表示方法。弧 a = (i , j )将用标号 a 进行索引，而不是用对应的结点对 (i , j )进行索引。弧的列表为二维数组 A ，其中 Aa1 = i ， Aa 2 = i 。在读入数据后（即弧集为已知）将定义流变 量。注意在下面的实现中，未采用数字对结点进行编号，而是用名称“Source”，“D2”， “C4”等，这样能够能够方便对结果进行解释。model E-2 Minimum cost flow uses mmxprsdeclarationsNODES: set of string! 结点集合MINQ : integer ! 运输总量A: array(ARCS:range,1.2) of string! 弧COST: array(ARCS) of integer! 每条弧的运输成本MINCAP,MAXCAP: array(ARCS) of integer! 弧的最小和最大通过量end-declarationsinitializations from e2minflow.datA MINQ MINCAP MAXCAP COSTend-initializations finalize(ARCS)! 计算结点集合NODES:= union(a in ARCS) A(a,1),A(a,2)declarationsflow: array(ARCS) of mpvar! 弧上的流end-declarations! 目标函数：总运输成本Cost:= sum(a in ARCS) COST(a)*flow(a)! 流平衡：入流等于出流forall(n in NODES | nSOURCE and nSINK)sum(a in ARCS | A(a,2)=n) flow(a) = sum(a in ARCS | A(a,1)=n) flow(a)! 最小和最大流通过量forall(a in ARCS | MAXCAP(a) 0) do flow(a) = MINCAP(a)flow(a) = MINQ! 求解此问题minimize(Cost)end-model在此模型中使用了另一个 Mosel 集合运算符：对所有由集合 ARCS 中的弧相连 接的结点进行 union（并集）运算从而得到结点集合 NODES。10.2.3 结果最低运输成本为 1,715 欧元。图 10.2 示意了此时的解决方案：在实际用于运输 的弧上标出了运输量，未使用的弧用虚线表示。例如，仓库 D1 的所有 50 吨库存都 将通过公路运输到回收中心 2。图 10.2：最优运输方案 应注意到，这种对弧上的流有最小约束的问题可能会无法找到可行解。在本例中，如果 MINQ = 9 ，则由于所有铁路运输的弧的最低通过量都是 10 吨，因此无法使用 铁路运输。10.2.4 扩展讨论这个模型可以用于求解任何类型的最小费用流问题。例如，可以为各个回收中心 设置需求量。对于回收中心 c ，可以将弧 (c,sin k )的流最小值设置为此需求量，从而保证能够满足需求。但是，若要求有解，则必须满足一个条件：仓库处的产品的可用 量总和须大于或等于回收中心的需求量总和。10.3 仓库位置设置 有一家大公司希望开设一些新的仓库，以向销售中心供货。每开设一个新仓库都有一些固定费用。货物将从仓库运输到附近的销售中心。每次运输的运费取决于运输 的距离。这两种类型的费用非常不同：仓库开设费用属于投资支出，通常在若干年后 将勾销，而运输费用属于运营成本。如何结合这两种费用不属于本书的讨论范围，我 们假定这两种费用可比，为此可能需要以年为单位计算运营费用。有 12 个可以建造新仓库的位置，并且需要从这些仓库向 12 个销售中心供货。 下表 10.3 给出了每个仓库完全满足每个客户（销售中心）需求所需的总成本（千欧元，不是单位成本）。因此，例如从仓库 1 向客户 9（根据表 10.5 可以看到此客户总需求量为 30 吨）供货的单位成本为 60000 欧元/30 吨，即 2000 欧元/吨。如果无 法进行送货，则对应的成本标记为无穷大 。表格 10.3：满足客户需求所需的运输成本 客户仓库123456789101112110080505060100120906070651102120906070651101401108080751303140110808075130160125100100801504160125100100801501901501305190150130200180150620018015010080505060100710080505060100120906070651108120906070651101401108080751309140110808075130160125100100801501016012510010080150190150130111901501302001801501220018015010080505060100此外，对每个仓库，还有如下信息：仓库建设的固定费用（需要计入目标函数）和仓库的容量上限，这些信息都列于表 10.4 中。表格 10.4：仓库建设费用和容量限制仓库123456789101112建设费用350090001000040003000900090003000400010000900035000容量上限300250100180275300200220270250230180表 10.5 列出了各个销售中心（客户）的需求量。表格 10.5：客户需求量数据客户123456789101112需求量120807510011010090603015095120任何时候都要保证满足客户需求，可以从多个仓库向同一个客户送货。应在哪些位置开办仓库才能使总的建设成本以及运输成本最低，同时仍然能够满足所有客户需 求？10.3.1 模型的数学表达为写出此问题的数学模型，我们用变量 DEM c 表示客户（销售中心） c 的需求 量，用 CAPd 表示仓库 d 的最大容量。建造仓库 d 的固定费用为 CFIX d ，从仓库 d 向 客户 c 运输一吨货物的运输成本为 COSTcd 。此外，令 DEPOTS 为所有可建造仓库 的位置的集合， CUST 为将要向其进行送货的客户集合。为求解此问题，我们需要了解将要在哪些位置开办仓库。因此可以定义一个二值 变量 build d ，如果在位置 d 处开办了仓库，则 build d 取值为 1，否则为 0。此外， 我们也需要知道有哪个或哪些仓库向某个客户供货。因此我们引入变量 fflowdc ，表示客户 c 从仓库 d 那里接受到的货物量占总需求量的比例。这些变量的取值范围为0,1，因此可以得到约束条件（10.3.1）。d DEPOTS ,c CUST :fflowdc 1（10.3.1）每个客户的需求都应完全满足：c CUST : fflowdc = 1（10.3.2）dDEPOTS现在我们需 要建模表示 出离开仓库 d 的货物总量 不可超过此 仓库的总容 量CAPd ，但如果此仓库尚未修建，则此流为 0。因此有约束条件（10.3.3）。d DEPOTS : DEM c fflowdc CAPd build dcCUST（10.3.3）现在我们来看看为什么可以这样表示。由于 fflowdc 是客户 c 从仓库 d 那里收到的货物占其总需求量的比例，因此 DEM c fflowdc 就是客户 c 从仓库 d 那里收到的货物量。如果仓库 d 已经开办（ build dCAPd ；如果仓库 d 尚未开办（ build d= 1 ），则从仓库 d 流出的货物总量不能超过= 0 ），则此货物出流值必须为 0。要最小化的总成本由仓库建设费用和运输费用两部分组成。即目标函数（10.3.4）由两个求和组成。这样完整的数学模型就可以写成：minmizeCFIX d build d +dDEPOTSCOSTdc fflowdcdDEPOTS cCUST（10.3.4）d DEPOTS ,c CUST :fflowdc 1（10.3.5）c CUST : fflowdc = 1dDEPOTS（10.3.6）d DEPOTS : DEM c fflowdc CAPd build d cCUST（10.3.7）d DEPOTS ,c CUST :fflowdc 0（10.3.8）d DEPOTS :build d N（10.3.9）10.3.2 模型实现上述数学模型可以很容易地改写为如下的 Mosel 程序。model E-3 Depot location uses mmxprsdeclarationsDEPOTS = 1.12! 仓库集合CUST = 1.12! 客户集合COST: array(DEPOTS,CUST) of integer! 运输成本CFIX: array(DEPOTS) of integer! 仓库建设固定成本CAP: array(DEPOTS) of integer! 仓库容量DEM: array(CUST) of integer! 客户需求量fflow: array(DEPOTS,CUST) of mpvar! 仓库供货量占客户需求总量百分比build: array(DEPOTS) of mpvar! 如果选择在某处建造仓库，则取值为 1! 否则为 0end-declarationsinitializations from e3depot.datCOST CFIX CAP DEMend-initializations! 目标函数：总成本TotCost:= sum(d in DEPOTS, c in CUST) COST(d,c)*fflow(d,c) +sum(d in DEPOTS) CFIX(d)*build(d)! 满足客户需求forall(c in CUST) sum(d in DEPOTS) fflow(d,c) = 1! 仓库容量限制forall(d in DEPOTS) sum(c in CUST) DEM(c)*fflow(d,c) = CAP(d)*build(d)forall(d in DEPOTS) build(d) is_binaryforall(d in DEPOTS, c in CUST) fflow(d,c) = 1! 求解此问题minimize(TotCost)end-model我们可以再加入一组约束条件来描述关系“如果从仓库 d 有货物运出，则应该修建此仓库”（以及其相反关系“如果仓库 d 未修建，则从此仓库没有货物运出”）。约 束条件（10.3.3）隐含表示了此关系，但我们加入的新约束条件（分离出的约束条件）能够使模型表达更紧密。即，向模型中加入了这些约束条件之后，线性规划松弛求解的结果将更接近混合整数规划的解。可以向模型直接加入这些新的约束条件，但由于 在上面的程序中已经完整地给出了此模型，因此我们可以将这些约束条件转化为下面 所示的模型剪辑（model cuts）形式。通过将这些变量表示为模型剪辑，我们可以让 优化器来决定是否使用这些附加的约束条件。以，用作模型剪辑的约束条件都应进行 命名，并在 Mosel 程序中进行全局声明，如下所示（Mosel 程序中线性约束条件的 类型未 linctr）。declarationsmodcut: array(DEPOTS,CUST) of linctr end-declarationsforall(d in DEPOTS, c in CUST) do modcut(d,c):= fflow(d,c) = build(d) setmodcut(modcut(d,c)end-do10.3.3 结果优化算法求得最低总成本为 18,103 千欧元。应在五个位置开设仓库，即位置 1，5，8，9，12。下表列出了从这些仓库向客户送货的方案。除了位置 5 上的仓库之外， 其他仓库都完全利用了库存能力。表格 10.6：运输方案 客户仓库1234567891011121-575100-120512040-8-35-100-85-9-110-6595-12-906030-10.4 燃油运输 有一个运输商需要将一些燃油从位于 Donges 的炼油厂运输到法国西部的一些客户那里。这些客户分别位于 Brain-sur-lAuthion，Craquefou，Gurande，HaieFouassire，Msanger，和 Ponts-de-C。下表列出了每个地方的需求量升数。表格 10.7：客户需求量（升）Brain-sur-CraquefouGurandeHaieMsangerPonts-de-ClAuthionFouassire140003000600016000150005000下面这个表中列出了炼油厂与客户之间的距离。表格 10.8：距离矩阵（千米）Brain-HaiePonts-Dongessur-Craquefou GurandelAuthionDonges014855327014073Brain-sur-lAuthion148093180991272Craquefou5593085208328Gurande3218085010017499Haie Fouassire70992010008549Msanger140128317485073Ponts-de-C7372289949730FouassireMsangerde-C此运输公司使用容量为 39000 升的油罐车进行运输。请选择运输路线，使向所有客户运输的总里程数最少。10.4.1 模型的数学表达这个问题可以看作注明的旅行商问题（TSP）的推广形式，我们在第 11.5 节中 将看到旅行商问题的另一个例子。在这个例子中，我们有多个“旅行商”，每个“旅 行商”的行程都需要从 Donges 出发，并最后回到 Donges。我们引入变量 precij ，如果在路线中城市 j 紧随城市 i ，则此变量取值为 1，否 则为 0。令 SITES = 1,K , NS 为地点集合。地点 1 即为此炼油厂，因此可以得到一个子集 CLIENTS = 2,K , NS，对应于我们送货的目标地点。令 DISTij 为两个城市i 和 j 之间的距离，DEM i 为客户 i 定购的燃油数量，CAP 为油罐车的容量上限。此 外也加入变量 quanti ，表示在通往客户 i 的路径上送出去的燃油总量，包括给客户 i 的燃油量。例如如果包含客户 10 的路径为 1，3，11，10，6，1，则 quant10 的值即为 DEM 3 + DEM 11 + DEM 10 。借助于这些符号，我们可以写出如下的数学模型：minmize DISTij precijiCLIENTS jSITES ,i j（10.4.1）j CLIENTS :i CLIENTS : precij = 1iSITES ,i j precij = 1jSITES , j i（10.4.2）（10.4.3）i CLIENTS :i CLIENTS :DEM i quanti CAPquanti CAP + (DEM i CAP )prec1i（10.4.4）（10.4.5）i, j CLIENTS ,i j :quant j quanti + DEM j CAP + CAP precij +jji(CAP DEM DEM i) prec（10.4.6）i CLIENTS :quanti