卡車裝載問題外文翻譯

1、<p>　　本科生畢業(yè)設(shè)計(jì) (論文)</p><p><b>　　外 文 翻 譯</b></p><p>　　北華航天工業(yè)學(xué)院教務(wù)處制</p><p>　原 文 標(biāo) 題A Truck Loading Problem</p><p>　譯 文 標(biāo) 題卡車裝載問題</p><p>　作者所在

2、系別經(jīng)濟(jì)管理系</p><p>　作者所在專業(yè)</p><p>　作者所在班級</p><p>　作 者 姓 名</p><p>　作 者 學(xué) 號</p><p>　指導(dǎo)教師姓名</p><p>　指導(dǎo)教師職稱</p><p>　完 成 時 間2011年10月</

3、p><p>　　注：1. 指導(dǎo)教師對譯文進(jìn)行評閱時應(yīng)注意以下幾個方面：①翻譯的外文文獻(xiàn)與畢業(yè)設(shè)計(jì)（論文）的主題是否高度相關(guān)，并作為外文參考文獻(xiàn)列入畢業(yè)設(shè)計(jì)（論文）的參考文獻(xiàn)；②翻譯的外文文獻(xiàn)字?jǐn)?shù)是否達(dá)到規(guī)定數(shù)量（3 000字以上）；③譯文語言是否準(zhǔn)確、通順、具有參考價(jià)值。</p><p>　　2. 外文原文應(yīng)以附件的方式置于譯文之后。</p><p><b>

4、　　附件：外文翻譯原文</b></p><p>　　A truck loading problem</p><p>　　1. Introduction</p><p>　　This research studies a truck loading problem and its mathematical properties, and consequen

5、tly develops a model and a solution method. 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 c

6、ompartment. The compartments may have equal or different volume capacities. The cargo space of a truck is divided into compartments for ease of unloading the full packages and loading the </p><p>　　An exampl

7、e of such operation is the transportation and delivery of the packaged soft drinks from a source to different destinations. In the European soft drink industry usually there are six types of product sizes (bottle sizes).

8、 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 destinations on a given route. A route is composed of a number of

9、destinations within a geographical region. In this </p><p>　　2. Problem definition</p><p>　　A truck with m compartments transports and delivers q different products in their own packed cases fro

10、m 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 o

11、f such an operation is the transportation and delivery of packaged soft drinks from a bottling plant or a warehouse (source) to a number of destinations such as restaurants, cafe</p><p>　　It is very importan

12、t to deliver the correct number of products at each demand point to meet the demand until the next delivery. A shortage of any product at any destination means lost business and/or additional deliveries with the existing

13、 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 will ha

14、ve to be repeated indefinitely with the s</p><p>　　The time interval within two consecutive deliveries is called the replenishment time.An operational problem is then how to load the compartments of the vehi

15、cle in a such a way to maximize the replenishment time for the given vehicle compartment capacities provided that the demand is satisfied until the next delivery on a specified vehicle route. Simultaneous depletion of th

16、e products is accomplished by delivering the correct proportions of the products at each destination. The destinations agree</p><p>　　2.1. A model for truck loading problem</p><p>　　The decision

17、 variables and relevant parameters are introduced before developing a model. The parameters of the problem are assumed constant.</p><p>　　The common replenishment time for all types of products at n differen

18、t 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 q

19、uantity (integer) of product 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 dest</p>

20、;<p>　　The objective then becomes how to load the vehicle in such away that the replenishment time (t) is maximized.</p><p>　　The mathematical model is now stated as follows:</p><p>　　Max

21、 t (3)</p><p>　　Subject to</p><p><b>　　(4) </b></p><p>　　， (5)</p><p&g

22、t;　　integer for (） (6)</p><p><b>　　(7)</b></p><p>　　This is a mixed integer linear programming (MILP) problem with m*n*q integer variables and one continuo

23、us 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 the compartment cannot exce

24、ed 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 delive</p><p>　　The term in this mod

25、el is the actual delivery quantity (integer) of the product for destination. In the model proposed by Yüceer (1997),is the delivery quantity of the product as the sum of the capacities of the compartments allocated

26、. Thus, there is a structural and a subtle difference 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

27、for all L=(j，k)J*K as follows:</p><p><b>　　Max t</b></p><p>　　Subject to </p><p><b>　　，</b></p><p>　　integer for（）</p><p>

28、　　However, setting yie=PL， dL=pd , , makes the model look simplified but yields erroneous results.</p><p>　　Subject to </p><p>　　integer for（）</p><p>　　Since xiL is a nonnegative

29、 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

30、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.</p&

31、gt;<p>　　2.2 A solution method</p><p>　　The vehicle loading problem (2)–(7) is a mixed integer linear programming problem (MILP). The commercial packages LINDO,LINGO, EXTENDED LINDO, HYPER LINGO, and

32、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 the p

33、roblem (computational performance of LINGO is given in Table 4). Therefore an efficient method based on the special stru</p><p>　　An investigation of the structure of the problem reveals that the constraints

34、 (4) and (5) of the problem are the constraints 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 t

35、he products and further details of WDP are presented in Appendix. This sub problem for a given t is stated mathematically as follows:</p><p><b>　?。?）</b></p><p><b>　?。?）</b&

36、gt;</p><p>　　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) an

37、d (9) can be obtained by an algorithm (sub algorithm 1) very easily. This sub problem is called the WDP in the article from this point on.</p><p>　　After this preliminary work, an approach to solve the MILP

38、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 another sub algorithm fo

39、r 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

40、 </p><p>　　Step 0. Initialize: and choose an and go to Step 1.</p><p>　　Step 1. , then call sub algorithm 1 and go to Step 2.</p><p>　　Step 2. If sub algorithm 1 finds a feasible s

41、olution to WDP for t=, then = otherwise . If , then go to Step 3, otherwise set and go to Step 1.</p><p>　　Step 3. For eachand,calculateand.Then call sub algorithm 2 for an optimality test and/or possible i

42、mprovement.</p><p>　　The weighted distribution problem (WDP) can be represented in a tableau form very similar to the transportation tableau. A dummy column may be introduced to take up the slack in each com

43、partment. The following simple algorithm obtains an integer and feasible solution to WDP of expressions (4), (5), (8) and (9) for a given t. It is similar to the north-west corner method with some additional features in

44、obtaining an integer solution.</p><p>　　3. Conclusions</p><p>　　This research studies a truck loading problem, its mathematical structures and properties. There are q different types of product

45、to be transported and delivered in a vehicle with m different compartments from a source to a n different destinations. The operational problem is then how to load the vehicle in a such way that the replenishment time is

46、 maximized. The sizes of the products can vary. Each product has a different volume of packaging. The compartments can have different capacities. The </p><p>　　An efficient heuristic procedure with a main al

47、gorithm and two sub algorithms is developed for solving the truck loading problem after investigating the special structure of this class of problems. The constraints 4,8,9 for a given replenishment time form the constra