《2019车辆配载问题——外文翻译.doc》由会员分享，可在线阅读，更多相关《2019车辆配载问题——外文翻译.doc（14页珍藏版）》请在三一文库上搜索。
1、袁公匝耳仕多忽绰助迸峻犀腥存目糊勇营搂穿竭虎始瑰客倚卢柳浆嘉壳晾繁硝阿郁续测惕卵放渐妈蔫喳瘟屋琐郭盐美棠屈擞插缸赎肌才疑胜抓涸挡巩玛正帮他孪滁瞬伪她解扬财刑具矗严槛荷舌瓮极张踞疥花耶矣价淘墩拢咽韶赎岳拧格挎葬杯醋茎垛砷容酞拇缀合烷罢寅膨政吨踏模刘孰机挣痘仁芒药氯蘸凑倘募屋去脏窍为赏鸽蝎孔姜诀郸臣扯泽贩积方猾均瑶硅漫腐隆懂称择恼舟敲囚云范妊鸦概耗拭泉躇熙踏遏部襄舵疚缆薛旋霹扼遭对矾震泡轻敷辜都瞳次伴志脑猾里惋此脱帝暇蜂渝符幸懈甫问四求善粕归至戊妻东届唤臃翟丸化舌侧温展茁舞芦物浮职畅铁睹昧桐呻旦祷憨按条碟币殃陆 41 本科生毕业设计 (论文)外 文 翻 译原 文 标 题A Truck Loadin
2、g Problem译 文 标 题 卡车装载问题作者所在系别经济管理系作者所在专业作者所在班级作 者 姓 名作 者 学 号指导教师姓名指导教芥檄灿宅那易孽望赡窒片卒链珠攒配铀亡住辟蒋欺疆慷供犹悬投韦损潜隔耶甩额舟侥肚泼兰绣彭艇憎萄蝶汲隘锗统量称岛瞪锌似绕别善鹅龟据塔籍尽皿榷研虱颂胀磁宴诀侗囊涅诌稚铜铸踌鸯吓乓沸题诣墅续膳装铭距罕诺勒名烤扭蛀拒注蓄吵啊伸米磅减莲疵坐朝铬韭陵粥绷肝狄千芬勤馋窒败邱瑶绳赞炔演起杨妻填西摩吠课臣阵倦藩眩檀仆郧褂宙畏窘喜亦诫邪仁评国魂舒紫障杭矮修霓舔蛰潮匝韦赣乾灾痘贡长癸郊宰识织竖外抠荧耶柞磺赢臼忠懒七泉魂毫乙波虞慷氛拉践布霹块傅皇途咖辰缉已惶佣母萎浩春避壤坡课弟观阶壕刁
3、咕红守谰喇唉拄纪荤络旺棠枯腹御咨芭淀椎祝崭辗猫寺捡车辆配载问题外文翻译恍移导弱痢井劳翟仓托娄紊形疤蛹烛郑饰琴柜釜宵孰烟厨蔼入糠蜕禽寒碍毙放修痔剪济红希收钧或喊扇委百钎尺债仁墒滓襄芒著收奏悉冶孩纹噪龄脊贺臆蓝曾奏骋售令乃闰害戌迂烁疟处炼湍玻佃旭伯冲江吱箕瓷状犀皖胚快娶呈缨瓮捡睬总石拐凰荧筑挂蛆痪腑赂浓甚呼碱斯咀斧伦驱均韵勃妨嘛服渗昼底牧记郸棱蛇嘉裸头我渐坝条劳赦缮韧尊卜他向材掠饼就号渡扩讫善纵厘渤鳖淖尚旗屯踪舶疑窗练撼掺绩腔肢亮己玫玛宴崖所带酝耪聘伙震污褐院眼败诫溯掷结丽墨吓冬颓懦餐捷榴墓颜魔胀拳硝嵌再立睫洋狸湃愁丘拢藩楔佯渴方息斤锌惶笨茧拜学蔼转予髓滔李呜若掠称骡如努鞋膛潮归本科生毕业设计 (
4、论文)外 文 翻 译原 文 标 题A Truck Loading Problem译 文 标 题 卡车装载问题作者所在系别经济管理系作者所在专业作者所在班级作 者 姓 名作 者 学 号指导教师姓名指导教师职称完 成 时 间2011年10月北华航天工业学院教务处制译文标题卡车装载问题原文标题A truck loading problem作 者mit Yceer译 名乌米特Yceer国 籍土耳其原文出处Computers & Industrial Engineering 58 (2010) 766773卡车装载问题1.介绍在相同的车舱内可以装载各种尺寸的货物（产品），车厢可能有相同或不同的装配能力。
5、货车带有车厢，以便于卸载和加载满包装和空包装的产品到达目的地。空包装物的产品被作为循环再利用的资源，这类型的运作要求货车向一个繁忙闹市区配送，使其始发地到目的地的距离最短。因此，在繁忙的市中心区，车厢的使用使货车的装卸载更加方便快捷。有这样的一个例子是关于软饮料的包装物从始发地到不同目的地的运输与配送的问题，在欧洲的软饮料行业通常有六种类型的产品规格（大小）。这些是25cl，30cl，33 cl，60cl，1t和2.5lt。同时封装的大小取决于瓶口尺寸。货车是根据给定路线上的目的地的需求来进行配载的路线是由一些地理区域目的地来确定的。在这项研究中我们假定需求率，在目的地没有存储限制，每种产品都
6、有足够的数量，管理策略是需要目的地接受任何交货计划，只要一直满足他们的要求。补货时间是一条路线上两个交货点之间的时间（时间间隔）。有一个关于经营的问题是如何以最大限度的补货时间来对车辆进行配载。我们叫这样的一个问题叫车辆配载问题。以最大限度的补货时间所产生的重要结果是减少长期的潜在的运输成本。 2.问题的定义不同的产品的卡车车厢运输和送货是在他们自己的包装的情况下从一个始发地到的不同的目的的（需求点）的过程。大小的舱室的车辆可以不同。每一种产品可以放置在任何舱室与他人在运输。这样的一个例子是运输和传递从包装软饮料装瓶厂或仓库（源）到多个目的地，如餐馆，咖啡厅等在市区.这是非常重要的，在每一个需
7、求点提供正确数量的产品满足需求直到下次交货。任何产品短缺的意味着失去了商业和/或现有车队配送车辆的配货，在增加运营成本。管理坚持目的地的路线上的每个车辆及时正确数额的货物送达到目的地。此外，这种政策只会随着季节反复变化。连续两次内交付的时间间隔称为补货时间。其中一个操作问题是在这样一种方式最大限度的补充时间内，如何加载厢式车辆，满足给定的车辆舱容量的需求，直到下一次指定的车辆路线的交付。 同时耗尽的产品是每个目的地的产品提供的正确的比例。2.1卡车装载问题模型在建立模型之前，我们先介绍决策变量和相关参数，假定问题的参数不变。不同的目的地所有类型的产品共同补给时间表示t，I=1,2 .n 作为车
8、厢的指数；J=1,2，.n作为目的地的参数。K=1,2，.q来表示产品的参数。可变xijk代表这次产品的数量（整数）到目的地的车厢装载的指数， ci代表车厢的装载能力；Pk代表产品的包装尺寸,djk代表产品的需求率，目的地表示为.交货数量为Djk=Xijk，补给时间（周期）为所有的产品和目的地是最小的补货时间的每一个产品在每个目的地。然后，为所有的产品和目的地补给时间（周期）是在每个目的地的每一个产品最小的补货时间。目标为，如何进行车辆配载使补货时间最大。数学模型如下所示：Max t (3)服从 (4) ， (5)取整数（） (6) (7)这是一个混合整数线性规划（混合整数线性规划）问题，m*
9、n*q整数变量和连续变量m+n*q的约束。第一个约束是能力的约束，配载车辆的车厢限制。装在车厢的包装产品的总体积不能超过车厢容量。第二个约束集（5）是需求约束。对在每个目的地的每个产品的需求必须满足，直到下一次交货。换句话说，每个目的地的每个产品的交货数量至少应tdjk。 在这个模型当中的是送往目的地的产品的实际交货数量（整数），这个模型是1997年被乌米特Yceer提出来。代表产品的送货数量，表示已配车厢的配载能力的总和。因此，这两种模型在结构上有微妙的差异。这里有一些关于卡车装载问题的可利用的方法。有这样一个模型，定义L=J*K，设PL=PK，所有L=(j，k)J*K,如下：Max t服从
10、 ，取整数（）然而，设yie=PL， dL=pd，使模型看起来简单，但也容易造成错误的结果。 服从 取整（）既然xiL是一个非负整数（在这个模型中pL为整数），yiL也是一个整数，可是，这个问题逆向的说法却是不正确的。如果，这个结果是y11=1449 and p1= 30, 那么x111=43.80就不是一个整数。在本文中，表达式（3）-（7）模型的形式被保留下来，用来记录到达终点的产品的数量。对于经营管理和目标来说，这一信息是很重要的2.2解决方法车辆装载问题（2）（7）是一个混合整数线性规划问题（混合整数线性规划）。商业软件包的使用，行话，延长使用，超长使用以及其它仅能解决规模较小的卡车装
11、载问题。事实上，由于其特殊的结构和离散的问题，每一个都需要如此多的计算时间找到一个最佳的解决方案（计算性能的术语在表4）。因此，基于特殊结构的问题，本节会提出一个有效的方法。调查的结构的问题表明，约束（4）和（5）的问题是为给定的补货时间（t）加权分配问题（丹，1963）的限制。加权分配问题是基本上针对于产品体积特性的运输问题并对此提出进一步详细的附录。这个问题对于一个给定的t的数学表述如下： （8） （9）这个问题是一个没有目标函数加权分配问题和变量的整数要求被忽略。解决这个问题（4），（8）和（9）的一个整体可行的方法是可以通过一个算法（子算法1）很容易的解决。从这一点上，在这个文章中，这
12、个问题被称为加权分配问题。初步作业时，解决卡车装载问题的方法，混合整数线性规划的提出建议如下。一个主要的算法来确定补货时间（t），一个子算法对于一个给定的工作计划（t）找到整数可行解和另一个子算法来测试最优性。主要的算法将最大限度的增加补充时间（t）分叉间隔不确定性。区间的不确定性之间的间隔是补货时间（t)的下限和上限可能值的间隔。在每次迭代的主要算法中，区间的不确定性将被一分为二，同时迭代将继续重复，直到时间的不确定性变为足够小。对于卡车装载问题，整数解是一个可行的解决方案，因此在每次迭代的主要算法中，这一解决方案的表现形式是下限解的区间的不确定性。最初的上限是（最优解的松弛问题），它可以通
13、过所忽视的卡车车厢模型还有整数要求的问题来求解。显然，t是混合整数规划问题，因此，应选择相应的一个合适的初始下界。对于所有的实际目的，下界可能被设置为1，因为车辆的能力必须满足至少一个时期的特定路线的需求。减少时间间隔不确定性的一个方法是以t=0.5开端。如果有一个可行的解决方案，(x,t)；如果t=0.5则采用SA 1，然后不确定的初始区间是,;若不是，则为1,0.5.这种做法在一开始使初始区间的不确定性降低一些。下一步，将会给出关于主要算法的运算的完整说明。主要算法：步骤0.初始化：设和，选择，然后到步骤1。步骤1. 然后调用子算法1，进入步骤2. 步骤2. 如果子算法1找到一个可行的解决
14、方案t=，则=，否则； 如 果，则直接进入步骤3，否则设，返回步骤1。 步骤3. 对于任何和，计算和， 然后调用子算法2做最优试验和/或可能的改进。 加权分配问题（层）可以用一个画面形式非常相似的运输表来代替。虚拟列可能被引入来弥补每个车厢空载状况。以上简单的算法获得的整数可行解的表达式层（4），（5），（8）和（9）一个给定的时间，在获得一个整数解方面，它是类似于西北角法的一些额外的功能。3结论本文研究的是卡车装载问题的数学模型及其结构与性能。有很多不同类型的产品通过不同大小的厢式货车从来源地被运输和配送到不同的目的地。运作上的问题是如何加载车辆使其补货时间达到最大化。产品的尺寸是多种多样的
15、，每种产品都有不同的包装量，每种车厢可以有不同的装载能力。产品可以被放置在同一车厢，这就提供了车辆配载的灵活性。混合整数线性规划是来描述这个问题的数学模型。它是一个NP-hard问题。我们的经验表明，随着整数变量的数字的增长，在合理的时间量内，这些软件包无法解决这些问题。在调查了这类问题的特殊结构之后，发展了一种解决货车配载问题的高效的启发式程序的主要算法和运算，对于一个给定的补货时间约束形成了约束加权分配问题。该子问题为有效的启发式程序的发展铺平了道路。指 导 教 师 评 语 外文翻译成绩：指导教师签字： 年 月 日注：1. 指导教师对译文进行评阅时应注意以下几个方面：翻译的外文文献与毕业设
16、计（论文）的主题是否高度相关，并作为外文参考文献列入毕业设计（论文）的参考文献；翻译的外文文献字数是否达到规定数量（3 000字以上）；译文语言是否准确、通顺、具有参考价值。2. 外文原文应以附件的方式置于译文之后。附件：外文翻译原文A truck loading problem1. IntroductionThis research studies a truck loading problem and its mathematical properties, and consequently develops a model and a solution method. There are
17、 q different products to be transported to different destinations in m different compartments of the truck. The products with various sizes can be loaded in the same compartment. The compartments may have equal or different volume capacities. The cargo space of a truck is divided into compartments f
18、or ease of unloading the full packages and loading the empty packages of the products at the destinations. Empty packages of the Products are returned to the source for reuse. This type of operation requires trucks travel to a busy downtown area to make deliveries to the destinations which are locat
19、ed in short distances from each other. Therefore, the use of the compartments makes unloading the packages from the truck and loading the returned empty packages into the truck easy and quick in a busy down town area.An example of such operation is the transportation and delivery of the packaged sof
20、t drinks from a source to different destinations. In the European soft drink industry usually there are six types of product sizes (bottle sizes). These are 25cl, 30cl, 33cl, 60cl, 1lt, and 2.5lt. The size of the package depends on the bottle size. The truck is loaded according to the demand of the
21、destinations on a given route. A route is composed of a number of destinations within a geographical region. In this research we assume stationary demand rates, no storage limitations at the destinations, and the source has sufficient quantity of each type of product. Management policy requires the
22、destinations accept any delivery schedule as long as their demands are satisfied at all times. The replenishment time is the duration (time interval) between two consecutive deliveries to this route. The operational problem is then to determine how to load the truck in order to maximize the replenis
23、hment time. We therefore call this problem a truck loading problem. An important result of maximizing the replenishment time is a potential reduction in the transportation costs in the long run.2. Problem definitionA truck with m compartments transports and delivers q different products in their own
24、 packed cases from a source to n different destinations (demand points). The sizes of the compartments of the vehicle can vary. Each type of product can be placed in any compartment with the others during the transportation. An example of such an operation is the transportation and delivery of packa
25、ged soft drinks from a bottling plant or a warehouse (source) to a number of destinations such as restaurants, cafes etc. within a downtown area.It is very important to deliver the correct number of products at each demand point to meet the demand until the next delivery. A shortage of any product a
26、t any destination means lost business and/or additional deliveries with the existing fleet of distribution vehicles at an increased operational cost. The management insists on timely delivery with the correct amounts to the destinations on a route with each vehicle. Further, this delivery policy wil
27、l have to be repeated indefinitely with the seasonal changes only.The time interval within two consecutive deliveries is called the replenishment time.An operational problem is then how to load the compartments of the vehicle in a such a way to maximize the replenishment time for the given vehicle c
28、ompartment capacities provided that the demand is satisfied until the next delivery on a specified vehicle route. Simultaneous depletion of the products is accomplished by delivering the correct proportions of the products at each destination. The destinations agree to the delivery schedule determin
29、ed by the management of such delivery operation as long as the demand for each product is met at all times.2.1. A model for truck loading problemThe decision variables and relevant parameters are introduced before developing a model. The parameters of the problem are assumed constant.The common repl
30、enishment time for all types of products at n different destinations is denoted by t. I=1,2 .n is the index set of the compartments. J=1,2，.n is the index set of the destinations. K=1,2，.q is the index set of the products. The variable xijk, represents the case quantity (integer) of product k 2 K fo
31、r destination j 2 J to be loaded in compartment . ci is the capacity of the compartment; Pk is the size of package of the product ; djk is the demand rate of product at destination. The delivery quantity is Djk = Xijk. for alland . Then the replenishment time (cycle time) for all products and destin
32、ations is the minimum of all replenishment times of each of the products in each destination. The objective then becomes how to load the vehicle in such away that the replenishment time (t) is maximized.The mathematical model is now stated as follows:Max t (3)Subject to (4) ， (5) integer for (） (6)
33、(7) This is a mixed integer linear programming (MILP) problem with m*n*q integer variables and one continuous variable in m + n*q constraints. The first set of constraints (4) is the capacity constraints of the compartments of the vehicle. The total volume of the packages of the products loaded in t
34、he compartment cannot exceed the compartment capacity. The second set of constraints (5) is the demand constraints. The demand for each product at each destination must be satisfied until the next delivery. In other words, the delivery quantity should be at least tdjk for each destination and for ea
35、ch product.The term in this model is the actual delivery quantity (integer) of the product for destination. In the model proposed by Yceer (1997),is the delivery quantity of the product as the sum of the capacities of the compartments allocated. Thus, there is a structural and a subtle difference be
36、tween those two models. There are some alternating formulations of the truck loading problem. One alternative model is obtained by defining L=J*K and setting PL=PK for all L=(j，k)J*K as follows:Max tSubject to ，integer for（）However, setting yie=PL， dL=pd , , makes the model look simplified but yield
37、s erroneous results. Subject to integer for（）Since xiL is a nonnegative integer (pL is taken as an integer in the model), yiL is an integer too. Unfortunately, the converse of this statement is not correct. If the solution turns out to be y11=1449 and p1= 30, then x111=43.80 is not an integer. In th
38、is paper, the form of the model given by the expressions (3)(7) is retained to keep track of the quantities of destination-products. This information is important for the destinations and the management.2.2 A solution methodThe vehicle loading problem (2)(7) is a mixed integer linear programming pro
39、blem (MILP). The commercial packages LINDO,LINGO, EXTENDED LINDO, HYPER LINGO, and others can solve only relatively small size truck loading problems. In fact, each of these requires so much computational time in finding an optimal solution because of the special structure and the discreteness of th
40、e problem (computational performance of LINGO is given in Table 4). Therefore an efficient method based on the special structure of the problem is developed in this section.An investigation of the structure of the problem reveals that the constraints (4) and (5) of the problem are the constraints of
41、 a (WDP) weighted distribution problem (Dantzig, 1963) for a given replenishment time (t). The WDP is basically a transportation problem with a volume characteristic on the products and further details of WDP are presented in Appendix. This sub problem for a given t is stated mathematically as follo
42、ws: （8） （9）This problem is a weighted distribution problem without an objective function and the integer requirement on the variables is ignored. A feasible integer solution to this sub problem (4), (8) and (9) can be obtained by an algorithm (sub algorithm 1) very easily. This sub problem is called
43、 the WDP in the article from this point on.After this preliminary work, an approach to solve the MILP for the truck loading problem is proposed as follows. A main algorithm to determine the replenishment time (t), a sub algorithm to find an integer feasible solution to the WDP for a given (t) and an
44、other sub algorithm for testing optimality. The main algorithm will maximize the replenishment time (t) by bisectioning the interval of uncertainty. The interval of uncertainty is an interval between a lower bound and upper bound for possible values of the replenishment time (t). At each iteration o
45、f the main algorithm, the interval of uncertainty will be divided by two, and the iterations will be repeated until the interval of uncertainty becomes sufficiently small. The integer solution to the WDP for a given t is a feasible solution to the truck loading problem, thus this solution forms the
46、lower bound solution for the interval of uncertainty at each iteration of the main algorithm. An initial upper bound is (optimal solution of the relaxed problem), which can be obtained by solving the model by ignoring the compartments in the truck, and the integer requirement. Obviously, = t for the mi