《卡车装载问题外文翻译.doc》由会员分享，可在线阅读，更多相关《卡车装载问题外文翻译.doc（11页珍藏版）》请在三一办公上搜索。
1、本科生毕业设计 (论文)外 文 翻 译原 文 标 题A Truck Loading Problem译 文 标 题 卡车装载问题作者所在系别经济管理系作者所在专业作者所在班级作 者 姓 名作 者 学 号指导教师姓名指导教师职称完 成 时 间2011年10月北华航天工业学院教务处制译文标题卡车装载问题原文标题A truck loading problem作 者mit Yceer译 名乌米特Yceer国 籍土耳其原文出处Computers & Industrial Engineering 58 (2010) 766773卡车装载问题1.介绍在相同的车舱内可以装载各种尺寸的货物（产品），车厢可能有相同
2、或不同的装配能力。货车带有车厢，以便于卸载和加载满包装和空包装的产品到达目的地。空包装物的产品被作为循环再利用的资源，这类型的运作要求货车向一个繁忙闹市区配送，使其始发地到目的地的距离最短。因此，在繁忙的市中心区，车厢的使用使货车的装卸载更加方便快捷。有这样的一个例子是关于软饮料的包装物从始发地到不同目的地的运输与配送的问题，在欧洲的软饮料行业通常有六种类型的产品规格（大小）。这些是25cl，30cl，33 cl，60cl，1t和2.5lt。同时封装的大小取决于瓶口尺寸。货车是根据给定路线上的目的地的需求来进行配载的路线是由一些地理区域目的地来确定的。在这项研究中我们假定需求率，在目的地没有存
3、储限制，每种产品都有足够的数量，管理策略是需要目的地接受任何交货计划，只要一直满足他们的要求。补货时间是一条路线上两个交货点之间的时间（时间间隔）。有一个关于经营的问题是如何以最大限度的补货时间来对车辆进行配载。我们叫这样的一个问题叫车辆配载问题。以最大限度的补货时间所产生的重要结果是减少长期的潜在的运输成本。 2.问题的定义不同的产品的卡车车厢运输和送货是在他们自己的包装的情况下从一个始发地到的不同的目的的（需求点）的过程。大小的舱室的车辆可以不同。每一种产品可以放置在任何舱室与他人在运输。这样的一个例子是运输和传递从包装软饮料装瓶厂或仓库（源）到多个目的地，如餐馆，咖啡厅等在市区.这是非常
4、重要的，在每一个需求点提供正确数量的产品满足需求直到下次交货。任何产品短缺的意味着失去了商业和/或现有车队配送车辆的配货，在增加运营成本。管理坚持目的地的路线上的每个车辆及时正确数额的货物送达到目的地。此外，这种政策只会随着季节反复变化。连续两次内交付的时间间隔称为补货时间。其中一个操作问题是在这样一种方式最大限度的补充时间内，如何加载厢式车辆，满足给定的车辆舱容量的需求，直到下一次指定的车辆路线的交付。 同时耗尽的产品是每个目的地的产品提供的正确的比例。2.1卡车装载问题模型在建立模型之前，我们先介绍决策变量和相关参数，假定问题的参数不变。不同的目的地所有类型的产品共同补给时间表示t，I=1
5、,2 .n 作为车厢的指数；J=1,2，.n作为目的地的参数。K=1,2，.q来表示产品的参数。可变xijk代表这次产品的数量（整数）到目的地的车厢装载的指数， ci代表车厢的装载能力；Pk代表产品的包装尺寸,djk代表产品的需求率，目的地表示为.交货数量为Djk=Xijk，补给时间（周期）为所有的产品和目的地是最小的补货时间的每一个产品在每个目的地。然后，为所有的产品和目的地补给时间（周期）是在每个目的地的每一个产品最小的补货时间。目标为，如何进行车辆配载使补货时间最大。数学模型如下所示：Max t (3)服从 (4) ， (5)取整数（） (6) (7)这是一个混合整数线性规划（混合整数线
6、性规划）问题，m*n*q整数变量和连续变量m+n*q的约束。第一个约束是能力的约束，配载车辆的车厢限制。装在车厢的包装产品的总体积不能超过车厢容量。第二个约束集（5）是需求约束。对在每个目的地的每个产品的需求必须满足，直到下一次交货。换句话说，每个目的地的每个产品的交货数量至少应tdjk。 在这个模型当中的是送往目的地的产品的实际交货数量（整数），这个模型是1997年被乌米特Yceer提出来。代表产品的送货数量，表示已配车厢的配载能力的总和。因此，这两种模型在结构上有微妙的差异。这里有一些关于卡车装载问题的可利用的方法。有这样一个模型，定义L=J*K，设PL=PK，所有L=(j，k)J*K,如
7、下：Max t服从 ，取整数（）然而，设yie=PL， dL=pd，使模型看起来简单，但也容易造成错误的结果。 服从 取整（）既然xiL是一个非负整数（在这个模型中pL为整数），yiL也是一个整数，可是，这个问题逆向的说法却是不正确的。如果，这个结果是y11=1449 and p1= 30, 那么x111=43.80就不是一个整数。在本文中，表达式（3）-（7）模型的形式被保留下来，用来记录到达终点的产品的数量。对于经营管理和目标来说，这一信息是很重要的2.2解决方法车辆装载问题（2）（7）是一个混合整数线性规划问题（混合整数线性规划）。商业软件包的使用，行话，延长使用，超长使用以及其它仅能解
8、决规模较小的卡车装载问题。事实上，由于其特殊的结构和离散的问题，每一个都需要如此多的计算时间找到一个最佳的解决方案（计算性能的术语在表4）。因此，基于特殊结构的问题，本节会提出一个有效的方法。调查的结构的问题表明，约束（4）和（5）的问题是为给定的补货时间（t）加权分配问题（丹，1963）的限制。加权分配问题是基本上针对于产品体积特性的运输问题并对此提出进一步详细的附录。这个问题对于一个给定的t的数学表述如下： （8） （9）这个问题是一个没有目标函数加权分配问题和变量的整数要求被忽略。解决这个问题（4），（8）和（9）的一个整体可行的方法是可以通过一个算法（子算法1）很容易的解决。从这一点上
9、，在这个文章中，这个问题被称为加权分配问题。初步作业时，解决卡车装载问题的方法，混合整数线性规划的提出建议如下。一个主要的算法来确定补货时间（t），一个子算法对于一个给定的工作计划（t）找到整数可行解和另一个子算法来测试最优性。主要的算法将最大限度的增加补充时间（t）分叉间隔不确定性。区间的不确定性之间的间隔是补货时间（t)的下限和上限可能值的间隔。在每次迭代的主要算法中，区间的不确定性将被一分为二，同时迭代将继续重复，直到时间的不确定性变为足够小。对于卡车装载问题，整数解是一个可行的解决方案，因此在每次迭代的主要算法中，这一解决方案的表现形式是下限解的区间的不确定性。最初的上限是（最优解的松
10、弛问题），它可以通过所忽视的卡车车厢模型还有整数要求的问题来求解。显然，t是混合整数规划问题，因此，应选择相应的一个合适的初始下界。对于所有的实际目的，下界可能被设置为1，因为车辆的能力必须满足至少一个时期的特定路线的需求。减少时间间隔不确定性的一个方法是以t=0.5开端。如果有一个可行的解决方案，(x,t)；如果t=0.5则采用SA 1，然后不确定的初始区间是,;若不是，则为1,0.5.这种做法在一开始使初始区间的不确定性降低一些。下一步，将会给出关于主要算法的运算的完整说明。主要算法：步骤0.初始化：设和，选择，然后到步骤1。步骤1. 然后调用子算法1，进入步骤2. 步骤2. 如果子算法1
11、找到一个可行的解决方案t=，则=，否则； 如 果，则直接进入步骤3，否则设，返回步骤1。 步骤3. 对于任何和，计算和， 然后调用子算法2做最优试验和/或可能的改进。 加权分配问题（层）可以用一个画面形式非常相似的运输表来代替。虚拟列可能被引入来弥补每个车厢空载状况。以上简单的算法获得的整数可行解的表达式层（4），（5），（8）和（9）一个给定的时间，在获得一个整数解方面，它是类似于西北角法的一些额外的功能。3结论本文研究的是卡车装载问题的数学模型及其结构与性能。有很多不同类型的产品通过不同大小的厢式货车从来源地被运输和配送到不同的目的地。运作上的问题是如何加载车辆使其补货时间达到最大化。产品
12、的尺寸是多种多样的，每种产品都有不同的包装量，每种车厢可以有不同的装载能力。产品可以被放置在同一车厢，这就提供了车辆配载的灵活性。混合整数线性规划是来描述这个问题的数学模型。它是一个NP-hard问题。我们的经验表明，随着整数变量的数字的增长，在合理的时间量内，这些软件包无法解决这些问题。在调查了这类问题的特殊结构之后，发展了一种解决货车配载问题的高效的启发式程序的主要算法和运算，对于一个给定的补货时间约束形成了约束加权分配问题。该子问题为有效的启发式程序的发展铺平了道路。指 导 教 师 评 语 外文翻译成绩：指导教师签字： 年 月 日注：1. 指导教师对译文进行评阅时应注意以下几个方面：翻译
13、的外文文献与毕业设计（论文）的主题是否高度相关，并作为外文参考文献列入毕业设计（论文）的参考文献；翻译的外文文献字数是否达到规定数量（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.
14、There are 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 compa
15、rtments for 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
16、are located 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 pac
17、kaged soft 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 deman
18、d of the 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 requ
19、ires the 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
20、 replenishment 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
21、their own 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
22、 of packaged 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
23、product at 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 p
24、olicy will 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
25、vehicle compartment 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
26、 determined 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 co
27、mmon replenishment 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
28、 k 2 K for 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 a
29、nd destinations 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 fo
30、r (） (6) (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 lo
31、aded in the 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 a
32、nd for each 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 diff
33、erence between 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
34、but yields 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 integ
35、er. In this 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 progra
36、mming problem (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 discreten
37、ess of the 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 const
38、raints of 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
39、 as follows: （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
40、is called 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 (
41、t) and another 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 it
42、eration of 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 f
43、orms the 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, =
44、t for the mixed integer programming problem. A suitable initial lower boundshould be chosen accordingly. For all practical purposes, the lower boundmay be set to 1 because the vehicle capacity must meet the demand of a given route for at least one period. One way to reduce the interval of uncertaint
45、y is to start with t=0.5. If there is a feasible solution(x，t)such that t=0.5 obtained by using SA1, then the initial interval of uncertainty is ,otherwise it is 1,0.5. This approach halves the initial interval of uncertainty at the start. The complete descriptions of the main algorithm and the sub
46、algorithms are given next.Step 0. Initialize: and choose an and go to Step 1.Step 1. , then call sub algorithm 1 and go to Step 2.Step 2. If sub algorithm 1 finds a feasible solution to WDP for t=, then = otherwise . If , then go to Step 3, otherwise set and go to Step 1.Step 3. For eachand,calculateand.Then call sub algorithm 2 for an optimality test and/o
