陆路运输问题.doc
《陆路运输问题.doc》由会员分享,可在线阅读,更多相关《陆路运输问题.doc(26页珍藏版)》请在咨信网上搜索。
1、第 10 章陆路运输在公路和铁路运输以及第 11 章中将要研究的航空运输中,都存在很多优化问题。 这陆路运输网络与航空运输网络之间的主要区别在于陆路运输的网络更为密集,参与 者更多。边境的开放和运输商之间的强烈的竞争都使得优化方法成为降低运输成本从 而能够从竞争中胜出得关键因素。第 10.1 节将给出一个车辆租赁问题,在其中为保持理想的车队大小,需要将汽 车在各个租赁代理处之间转运,并需要使费用最小。在 10.2 节中描述了一个在不同 运输方式之间进行分配的问题:需要将给定量的货物从网络中的一个结点运输到另一 个结点,在此网络中存在多种运输方式,每种方式的成本和运输能力均已知。第 10.3 节
2、将处理一个战略层次的经典问题,即如何为仓库选址才能够最小化开办仓库和向客 户运输的成本。在 10.4 节中,我们将解决一个最优化燃油运输路径的问题。在第 10.5 节中描述了一个多种运输方式组合(联合运输)的问题,此问题与 10.2 节中的问题 的不同之处在于更换运输方式时也会带来一定费用支出。本章的最后一节中将研究一 个如何对整个车队进行规划的问题。10.1 汽车租赁 有一家小型汽车租赁公司,此公司有 94 辆可供出租的汽车,分布于 10 个代理点中。每个代理点的位置都将以地理坐标 X 和 Y 的形式给出,单位为千米。我们假 定两个代理点之间的距离约为它们之间欧氏距离(即最短距离)的 1.3
3、 倍。下表给出 了各个代理点的位置坐标,以及第二天早晨汽车租赁的需求量和前一天晚上各个代理 点拥有的汽车数。表格 10.1:车辆租赁代理点信息代理点12345678919X 坐标0201830353355112Y 坐标02010120252710015汽车需求量10681197157912当前拥有量813481221411157假定汽车转运的成本为每辆车每千米 0.50 欧元,请找出如何在各个代理点之间调度分配汽车才能够满足各处的需求,并且使转运成本最低。10.1.1 模型的数学表达对于代理点集合 AGENTS 中的每个代理点 a 我们都用 X a 和 Ya 表示其地理坐 标。 REQa 表示
4、在代理点 a 处汽车的需求量, STOCK a 为此代理点当前的汽车保有量。这两个值之间的差值即表示此处汽车数富余(如果为正数值),或者不足量(负值 )。此问题即找出车辆富余的代理点集合 EXCESS 和车辆不足的代理点集合 NEED 之间的最小费用车辆流。由于总富余量等于总不足量,因此必定存在能够满 足各处需求的车辆流。首先,我们定义变量 moveab 表示在两个代理点之间的车辆流:a EXCESS ,b NEED :moveab N(10.1.1)每个车辆富余的代理点都需要将其富余的车辆发送到别处(10.1.2),每个车辆不足的代理点都需要从别处接受到数量等于不足数量的车辆(10.1.3)
5、。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),其特征在于都有一组来源的,拥有数量有限的资源,以及一组需要此资源的目的地。对于最小费用流问 题
6、,通常可以采用单纯形算法求解线性规划从而找到整数解。因此约束条件(10.1.1) 可以用简单的非负约束条件取代。10.1.2 模型实现上述数学模型可以实现为下面的 Mosel 程序。在读入数据之后,我们首先检查 当前汽车的总保有量是否等于汽车的需求量,如果不相等,则停止此程序。如果相等, 则分别找出车辆富余和车辆不足的代理点集合。在下面声明决策变量数组和距离矩阵 时将用到这两个集合。model E-1 Car rental uses mmxprsdeclarationsAGENTS = 1.10 ! 汽车租赁代理点REQ: array(AGENTS) of integer! 汽车需求数量STO
7、CK: 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 w
8、riteln(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 E
9、XCESS,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
10、 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 选择运输方式 在法国西南
11、部有一家公司,这家公司需要将 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 运输,运费分别为
12、4 欧元/吨和 5 欧元/吨。仓库 D4 可以通过铁路或公路向回收中心 C2 运输,运费分别为 11 欧元/吨和 14 欧元/吨,或 者通过铁路或公路向回收中心 C3 运输,运费分别为 10 欧元/吨和 14 欧元/吨。此公司与铁路公司签订的化学物品运输合同规定,每次运输量至少应为 10 吨, 最多为 50 吨。除了标准的安全规章之外,对公路运输不存在其他特殊的限制。那么 此公司应如何运输这 180 吨化学物品才能够使总运费最低?10.2.1 模型的数学表达我们将把此问题建模为一个具有固定总通过量的最小费用流问题(minimum cost flow problem)。我们先来构造一幅图 G =
13、 (NODES , ARCS )。首先向结点集合NODES 中加入一组结点,代表各个仓库,然后再加入一组结点,代表回收中心(参 照图 10.1)。弧集合 ARCS 中包含了在所有仓库和回收中心之间可能存在的连接。运输方案即对应于图 G 中的一个流,即在每一条弧 (i , j )上的流 flowij 。弧 (i , j )具有一个最小通过量 MINCAPij(除铁路运输其他均为 0),一个最大通过量 MAXCAPij(即 运力上限,除铁路运输外均为无穷大),以及每吨的运输成本 COSTij 。从一个仓库到一个处理中心之间的两种运输方式需对应两条不同的弧。在这样的图中,两个结点之间至多有 p 条弧
14、,称为 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:运输网络图在此图
15、中未将仓库的存储量纳入考虑。为此,我们创建一个源结点(假想的结点1),此结点将用弧 (1,d ) 连接到每个仓库结点 d 上,且此弧的通过量为 MAXCAP1d , 对应于仓库 d 处的存储量。因此离开仓库 d 的流不会超过此值。为方便数学模型的表达,我们也创建一个宿结点(假想的结点 15),并且连接到每个处理中心结点上。 这样最终得 到的图即可 以表示为图 10.1,其 中 每条弧 (i , j ) 都对应于一个三 元 组(MINCAP ,MAXCAP ,COST)。“-”表示通过量为无穷大。ijijij在此数学模型中包含了流守恒约束条件(10.2.2),也称为 Kirchhoff 定理:每
16、个结点处的入流都等于此结点处的出流(除了源和宿结点之外)。每条弧上的流都至少取值为 MINCAPij (约束条件(10.2.3),且不超过最大通过量 MAXCAPij (约束条 件(10.2.4)。式(10.2.5)对总流量加以约束,即 MINQ = 180 吨。这样就迫使离开源(结点 1)的流总量等于 MINQ 。由于在此网络中流保持守恒,因此也可以使 用宿结点的入流总量等于 MINQ 作为约束条件。在这个约束条件中,我们可以将等号替换为 号,由于在最小化总成本时也将最小化总流量,因此此时总运输量将取此 下界值。最后要解释一下目标函数(10.2.1)。 COSTij 是每吨的运费成本,因此通
17、过弧 (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 MAXCAP
18、ij(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 的和。每种运输方式的最小和最大运力限制将表示为对应变 量 trasnp
19、ort dcm 的上界和下界约束条件,这一点与上述的(10.2.3)和(10.2.4)很相似。对于我们这个问题,这种表达方式可能比基于图的模型表达要容易一些。但在后面的模型实现和进一步的讨论中,我们仍然使用这种更一般的最小费用流模型,即(10.2.1)到(10.2.5)给出的模型。10.2.2 模型实现从这个问题可以引出一个经典的问题,即图的编码。可以将图定义为 N N 的 矩阵形式,其中 N 为结点总数,并为每对由弧相连的结点 (i , j )都定义一个流变量。 然而,对于稀疏图,如我们所使用的这个图,更常用(效率也更高)的方法是将图表示为弧的列表的形式。在下面的 Mosel 程序实现种就使
20、用了这种表示方法。弧 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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 陆路 运输 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。