外文原文
Dispatching Problems in Transport Logistics
It is the goal of optimization to adopt a system behavior in order to maximize or minimize an objective function. In economic systems, this objective function refers to revenue maximization. Logistics is a classical area of application for optimization, because it includes multiple complex optimization problems. In transport logistics, these complex problems often refer to tour planning and routing problems. The goal of transport is, to pick up goods at their origin and deliver them to their destination to overcome special distances in order to fulfill the six objectives of logistics: to deliver the right object (1) at the right time (2) to the right place (3) in the right quantity (4) and quality (5) at the right price (6) (Juuml;nemann, 1989, p. 18). Consequently, most logistics problems require multicriteria optimization taking into account several constraints.
This chapter introduces tour planning and routing problems in transport logistics and focuses on the most relevant problem variations and established approaches to solve them. Therefore, the problems are cat- egorized in three groups. Firstly, Section 2.1 presents the well-known Traveling Salesman Problem (TSP) with various constraints which has the objective of determining the shortest route for a single vehicle which includes all stops and fulfills additional constraints. Section 2.2 describes multivehicle variants of the Vehicle Routing Problem (VRP). Its main difference is that not only the shortest tour, but also the optimal allocation of goods to vehicles must be determined. Section 2.3 presents the dynamic variant of the VRP. Since there are numerous domain-dependent variations of each problem and at least as many approaches to solve them, comprehensive overviews are referenced. Formal descriptions of mathematical programs are provided as long as they are relevant in subsequent chapters. Section 2.4 concludes the chapter and discusses the limitations of applying classic approaches in dynamic real-world and Industry 4.0 applications.
2.1 Traveling Salesman Problems
The most famous problem in logistics is probably the Traveling Sales-man Problem (Flood, 1956), which is NP-complete (Garey, Graham, and Johnson, 1976). The classical TSP can be defined as follows.
Definition 2.1 (Traveling Salesman Problem). Let S denote a set of stops, which must be visited. Given the costs cvi,j for traveling from i isin; S to j isin; S and choosing indicator variables
the objective function of the classical TSP is
subject to
The objective function defined by Eq. 2.2 minimizes the overall cost. Eq. 2.4 and Eq. 2.5 ensure that each service request has to be satisfied exactly once. In addition, Eq. 2.6 is a sub-tour elimination constraint which guarantees that all stops are visited in a single and connected tour. In short, the goal is to find the shortest tour of a vehicle, which ensures that all service requests are satisfied.
In most real-world scenarios, time window constraints as well as time consumption at the warehouse/customer have to be considered. The Traveling Salesman Problem with Time Windows (TSPTW) which also involves handling times can be defined as follows.
Definition 2.2 (TSP with Time Windows and Handling Times). If ls denotes the latest pickup/delivery time at stop s isin; S , ts the time consumption of the loading or unloading process, r s the release time at s, and timei,j vehiclersquo;s time for driving from i to j, then
has to be fulfilled.
Let DEP sube; S denote a set of depots. In some TSPTW it is relevant that the vehicle starts and ends at a depot d isin; DEP . This is ensured by the following equations.
and
In some TSPs capacity constraints have to be considered.
Definition 2.3 (TSP with Capacity Constraints). Let CC s denote the current capacity of the vehicle at stop s isin; S and M the maximum capacity of the vehicle, then
has to be fulfilled.
Of course, there are problems which include time windows, handling times (Eq. 2.7), and capacity constraints (Eq. 2.10) at the same time. In addition, there are TSPs with pickup and delivery requests at the stops. If the transport is offered between a central depot and customers, it is not relevant which kind of service is offered at a stop as long as the maximum allowed capacity of the vehicle is not exceeded at any stop (Eq. 2.10). However, if the problem includes transports between customers in direct tours, the vehicle has to ensure that it visits the pickup stop before the delivery stop. This kind of Traveling Salesman Problem with Pickup and Deliveries (TSPPD) can be defined as follows.
Definition 2.4 (TSP with Pickups and Deliveries). Stops are a super set of a subset of pickup stops P sub; S \ ( D cup;DEP ) and a super set of a subset of delivery stops D sub; S \ ( P cup;DEP ). Moreover, O denotes a set of orders. An order o isin; O contains exactly one pickup stop po and one delivery stop do . Therefore, it must be ensured that the vehicle visits the pickup stop before the delivery stop by
Definitions 2.1 to 2.4 describe the TSP with frequently considered constraints. Nevertheless, there could be numerous additional constraints, especially in real-world problems. For instance, Jaillet (1988) solves the TSP with probabilistic customer demands and Malandraki and Dial (1996) present a dynamic programming heuristic for solving the time-dependent TSP.
The TSP and its variations are among the most investigated problems in mathematics, Operations Research (OR), and computer science, because the TSP is NP-hard, easy to describe, and hard or even impossible to solve optimally. There are numerous
全文共32003字，剩余内容已隐藏，支付完成后下载完整资料
译文
运输物流中的调度问题
采用系统行为来最大化或最小化目标函数是优化的目标。在经济系统中，这个目标函数指的是收入最大化。物流是一个经典的优化应用领域，因为它包含多个复杂的优化问题。在运输物流中，这些复杂的问题往往涉及到旅游规划和路线选择问题。运输的目的是,在他们的起源和提货送到目的地克服特殊的距离来实现物流的六项目标:将在正确的时间(1)正确的对象(2)正确的地方(3)正确的数量(4)质量(5)在正确的价格(6)(Junemann, 1989年,p . 18)。因此，大多数物流问题需要考虑多个约束条件的多准则优化。
本章介绍了运输物流中的旅游规划和路线问题，重点介绍了最相关的问题变化及其解决方法。因此，问题被划分为三组。首先，第2.1节给出了具有各种约束条件的著名旅行商问题(TSP)，其目标是确定包含所有站点并满足附加约束条件的单车最短路径。第2.2节描述了车辆路径问题(VRP)的多变量。其主要区别在于，不仅要确定最短的行程，而且要确定最优的车辆货物分配。第2.3节介绍了VRP的动态变化。由于每个问题都有许多依赖于领域的变体，并且至少有同样多的方法可以解决这些变体，所以需要引用全面的概述。数学程序的正式描述将在后面的章节中提供，只要它们是相关的。第2.4节总结了本章，并讨论了在动态现实和工业4.0应用程序中应用经典方法的局限性。
2.1旅行推销员问题
物流中最著名的问题可能是旅行推销员问题(Flood, 1956)，它是NP-complete (Garey, Graham、Johnson，1976)。经典TSP可以定义为:
定义2.1 (旅行推销员问题). 让S表示一组必须访问的站点。给定从iisin;S到jisin;S，并选择指标变量的代价cvi,j
经典TSP的目标函数为
得
由式2.2定义的目标函数使总成本最小化。Eq. 2.4和Eq. 2.5确保每个服务请求必须被精确地满足一次。此外，Eq. 2.6是一个子行程消除约束，它保证所有的站点都是在一个单独的和连接的行程中访问的。简而言之，我们的目标是找到车辆最短的行驶路线，从而确保满足所有服务请求。
在大多数实际场景中，必须考虑仓库/客户的时间窗约束和时间消耗。具有时间窗的旅行商问题(TSPTW)也涉及处理时间，可以定义为:
定义2.2 (TSP与时间窗口和处理时间). 如果ls表示停sisin;s处的最新取/交车时间，则ts为装卸过程的时间消耗，rs为s处的放行时间，时间i为j辆车从i行驶到j的时间，则
必须得到满足。
使DEP sube; S表示一组仓库。在某些TSPTW中，车辆的起点和终点disin;DEP是相关的。这可以通过下面的方程得到保证。
且
在某些TSP中，必须考虑容量限制。
定义2.3 (容量受限的TSP). 设CC s表示停sisin;s处车辆当前通行能力，M为车辆最大通行能力，则
必须得到满足。
当然，同时也存在时间窗、处理时间(Eq. 2.7)和容量约束(Eq. 2.10)等问题。此外，在各站点还有带取件和送货请求的tsp。如果运输是在中央车辆段和客户之间进行的，只要车辆在任何一站的最大允许载客量不超过(Eq. 2.10)，在一站提供何种服务就无关紧要。但是，如果问题包括客户之间的直接旅行，则车辆必须确保在交付前访问了取货站。这种旅行商接货问题(TSPPD)可以定义为:
定义2.4 (TSP与皮卡和交付). 停止一个超级组的子集皮卡停Psub;S \ (Dcup;DEP)和一个超级组交付的一个子集停止Dsub;S \ (Pcup;DEP)。此外，O表示一组订单。 一组订单 o isin; O包含一个拾取站po和一个交付站do。因此，必须确保车辆在送货前先到达取货站
定义2.1至2.4描述经常考虑约束的TSP。然而，可能会有许多额外的限制，尤其是在实际问题中。例如，Jaillet(1988)用概率客户需求求解TSP, Malandraki和Dial(1996)提出了一种求解时间依赖TSP的动态规划启发式算法。
TSP及其变化是数学、运筹学(OR)和计算机科学中最常被研究的问题之一，因为TSP是NP-hard，易于描述，而且很难甚至不可能最优地解决。求解带有各种约束条件的TSP的方法有很多，如遗传算法(Grefenstette, Gopal, Rosmaita, and Van Gucht, 1985);波特凡,1996;模拟退火(Aarts, Korst, and van Laarhoven, 1988;耿，陈，杨，施，赵，2011)，tabusearch (Fiechter, 1994;Gendreau, Guertin, Potvin和Taillard, 1999;Gendreau, Laporte, and Semet, 1998)，蚁群系统(Dorigo and Gambardella, 1997)，粒子群算法(Shi, Liang, Lee, Lu, and Wang, 2007)，神经网络方法(Potvin, 1993;Crrsquo;eput和Koukam, 2009)， kopt改进启发式(Lin和Kernighan, 1973;以及分支定界算法(Padberg and Rinaldi, 1991;菲舍蒂，萨拉查·冈萨雷斯，托特，1997;Hern #39; andez-P #39; erez and Salazar-Gonz #39; alez, 2004;Cordeau, Iori, Laporte, and Salazar Gonz #39; alez, 2010)具有几种上界和下界的启发式(Karp和Steele, 1985;Miller和Pekny, 1991;Johnson and McGeoch, 2007)，仅举几个例子。对TSP的全面回顾由Applegate, Bixby, Chvatal, and Cook(2006)和Cook(2012)提供。
2.2车辆路径问题
车辆路径问题(VRP) (Dantzig and Ramser, 1959)是包含多辆车辆的TSP的推广。TSP的目标是为一辆车找到最短路径，VRP的目标是为每辆车找到最优的货物分配和最短路径，两者都能使总成本最小化。VRP是np难题(Lenstra and Kan, 1981)。即使是最优的25-50个止损点也很难解决小问题(Azi, Gendreau, and Potvin, 2010)。
与定义2.1相似，VRP的定义如下。
定义2.5 (车辆路径问题). 使V表示一组车辆。给定车辆visin;v从iisin;S行到jisin;S并选择指标变量的代价cvi;j
VRP的最高优先级目标函数是通过
第二重要的是将车辆的成本降到最低，这通常取决于车辆行驶的距离或行驶的时间
得
根据附加的约束条件，每辆车v2v也必须满足Eq. 2.7 - Eq. 2.11。
如果VRP还包括客户之间的直接旅行，而不需要在中心仓库进行任何处理操作，则称为提货和交付问题(PDP)。经典的PDP考虑的是各种货物的运输，而所谓的“拨号乘车问题”(DARP) (Cordeau和 Laporte, 2007)或残疾人运输问题(Toth and Vigo, 1997)则涉及客运和其他目标函数，如最小化乘客的运输时间。
在未配对的PDP中，运输的货物是均匀的，可以交换的。因此，任何项目都可以交付给任何客户。在成对的pdp中，每一项都有一个特定的发送者和接收者。因此，订单o的取货和送货请求必须由同一辆车v处理
包含多个仓库的问题(Renaud、Laporte和Boctor, 1996)可以被认为是上面描述的PDP的专门化。一般来说，VRPs的可能约束的变化与TSP的相似。例如，软时间窗存在问题(Balakrishnan, 1993;Taillard, Badeau, Gendreau, Guertin, and Potvin, 1997)和概率客户需求的问题(Gendreau, Laporte, and Srsquo;eguin, 1996)。特别是在实际问题中，依赖于领域的约束和需求会增加复杂性。例如，拥有一个异构的车队需要在旅游规划过程中考虑车辆的个别属性。他们的能力各不相同。他们每公里的费用不同。他们有各自的工作时间。一些货运公司收取佣金，而另一些则收取固定费率。此外，负荷通常比科学调查中假定的更加个性化。货物不仅在取货或交货时间窗口和重量上不同，而且在价值、优先级和体积上也不同。此外，必须满足收费和危险货物限制以及海关的安全准则。图2.1给出了静态VRP解决方案的抽象说明。
定理2.1 (VRP的复杂性). 设k为车辆数减1 (k = |V| - 1)， n为必须停靠的站点数(n = |S|)。那么，VRP可能的参观次数最多(n k!)/k!= O (n !(n k) k)。
证明：为了说明一般VRP的复杂性和可能的解决方案的数量，请想象一个书架，您必须在上面堆放许多书。此外，书架可以用隔板分成几个部分。在本例中，图书表示必须访问的站点数量(表示为n)，每个部分表示车辆。因此，有|V|切片和|V| - 1分离器(记为k)，如图2.2所示。如果没有分隔符，就只有一个车辆和n!把书堆在一起。如果只有一个分隔符，那么就有n!(n 1)/1个组合(所有可能的图书组合都源于此)
图2.1: 静态VRP解决方案的抽象可视化，包括拾取和交付。
图2.2: 图中显示了一个VRP的插图，其中3辆车和9个站点应用于书架示例。有1320种可能将书分配到被分隔符分隔的部分。换句话说，有((9 3)/3)个组合来放置这3个分隔符!书的位置的排列。
表2.1: 该表显示了非常小的通用vrp可能的组合数。注意，如果订单有取货和送货的问题，例如，只需要10个站点就可以运送5个订单。
分隔器的不同位置)。如果有两个分隔符，则有n!((n 2)/2)个组合。因此，对于k个分隔符，有n!((n k)/k)组合。值n!((n k)/k)可以转换为
求解VRP的最优方法通常采用分支定界技术，由于计算量大，限制于求解小问题。例如，Ropke, Cordeau和Laporte(2007)提出了一种包含96阶PDPs的精确求解方法。Azi等人(2010)的求解器计算了25-50个停止点的VRPs的最优解。在过去的几十年里，已经开发了许多有效的启发式和元启发式来解决大型的VRPs和pdp，如禁忌搜索(Garcia, Potvin, and Rousseau, 1994;Rochat and Taillard, 1995;Taillard等，1997;Cordeau and Laporte, 2003)，遗传算法(Potvin and Bengio, 1996;Tan, Lee, Ou, and Lee, 2001;Berger和Barkaoui, 2004;Bruml;aysy, Dullaert, and Gendreau, 2004;Pankratz, 2005)，大型社区搜索(Shaw, 1998;Ribeiro和Laporte, 2012)，模拟退火(Bent和Hentenryck, 2006)，和ant系统(Gambardella, Eric #39; Taillard, and Agazzi, 1999;Bar #39; an和Schaerer, 2003;仅举几个例子。综合和推荐的解决方案方法，解决多种变化的VRPs提供了概述，如Bruml;aysy和Gendreau (2005a)， Bruml;aysy和Gendreau (2005b)， Golden, Raghavan，和Wasil(2008)，和Parragh, Doerner，和Hartl (2008a,b)。
克拉克和赖特(1964)的早期出版物应用了所谓的节约启发式。该算法将每个订单分配给只能传输相应订单的车辆。在接下来的迭代中，只要满足所有的约束，两辆车的旅程就被合并到一个单独的旅程中。这个过程一直持续到达到车辆的最大容量。一个经常被应用和建立的用于构建旅游的启发式是由Solomon(1987)开发的基于储蓄启发式的顺序插入启发式I1。Solomon的算法或其变体被上面提到的几个元启发式算法以及第3.4节中描述的许多基于多agent的方法所应用。所罗门算法最初创建了一个只包含高约束顺序的新循环。使用受约束的顺序(而不是受较少约束的顺序)可以在以下步骤中增加插入更多受较少约束的顺序的概率。其次，对每一个尚未插入的顺序，计算最小成本和最优的位置，在构建的旅游。成本最低的订单插入到相应的位置。此过程将继续，直到订单的约束禁止插入任何附加订单为止。序列插入启发式I1的目标是通过满足所有约束条件，使传输所有订单所需的车辆数量最小化。此外，Solomon(1987)提出了顺序插入启发式I2来最小化驱动距离，顺序插入启发式I3来最小化客户的等待时间。一些作者，如Dullaert和Bruml;aysy(2003)、Potvin和Rousseau(1993)以 Balakrishnan(1993)，对插入算法进行了改进，例如，允许并行插入、
全文共10693字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[450123]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
