دانلود مقاله ترجمه شده خواسته تصادفی و پنجره زمانی در مسیریابی وسایل نقلیه دارای ظرفیت – مجله الزویر

بخشی از ترجمه:

مسئله ی مسیریابی خودرویی واجد شرایط با استفاده از تقاضاهای تصادفی و پنجره های زمانی را می توان یک مسئله ی توسعه یافته از مسئله ی مسیریابی خودرویی واجد شرایط با تقاضاهای تصادفی دانست، که در آن تقاضاها به صورت تصادفی بوده و یک پنجره ی زمانی نیز بر روی هر رأس اعمال می شود. خطای رأس که به دلیل فزونی یافتن تقاضای ادراک شده ایجاد می شود، ممکن است یک واکنش زنجیری از خطاها را بر روی سایر خودروها و در همان مسیر به دلیل وجود پنجره ی زمانی، تحریک کند. این مقاله، به مدل سازی این مسئله به عنوان یک برنامه ی استوکاستیک یا تصادفی با منابع پرداخته و یک روش جستجوی هیروستیک را همسایگی انطباقی را به عنوان راه حل ارائه می دهد. در آزمایشات، از روش نمونه های بنچ مارک Solomon تغییر یافته استفاده شده است. نتایج محاسباتی به وضوح نشان می دهند که روش هیروستیک پیشنهادی ما نسبت به روش های دیگر، برتری هایی را به همراه دارد.

بخشی از مقاله انگلیسی:

abstract The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach. & 2011 Elsevier Ltd. All rights reserved. 1. Introduction The problem discussed in this paper is the capacitated vehicle routing problem with stochastic demands and time windows (CVRPSDTW), an extension of capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSDTW is defined on an undirected graph G¼(V,E), where V¼{v0, v1,y,vn} is the vertex set and E ¼ fðvi,vjÞ : vi,vj AV,iojg is the edge set. Vertex v0 is a depot at which are based m identical vehicles of capacity Q, while the remaining vertices represent customers. A symmetric travel cost matrix C¼(c(vi, vj)) is defined on E. We assume that all vehicles travel at unit speed and that travel costs are equal to distances. A service time is incurred when visiting a vertex. Each vertex vi is associated with a nonnegative and stochastic demand xi to be collected. The stochastic demands are splittable and unknown until vehicles arrive at the vertices. As a result, failure may occur along a route if the total collected demand exceeds the vehicle capacity. The CVRPSD can be cast as a stochastic mathematical program. There exist two main solution concepts in stochastic programming: chance constrained programming (CCP) and stochastic programming with recourse (SPR). In CCP, the problem is solved by imposing a constraint ensuring that the probability of route failure is bounded by some parameter. Stewart and Golden [1] and Laporte et al. [2] have shown that the CVRPSD can be transformed into an equivalent deterministic problem. This result also applies to the CVRPSDTW because the only stochastic component of the problem concerns demands. In SPR, two main solution strategies are available: a priori optimization [3–۱۰] and re-optimization [11,12]. The a priori optimization strategy is dominated in terms of solution quality by re-optimization, but the first strategy is preferable in terms of computational effort and can produce more stable and practically predictable solutions [4]. In a priori optimization, a first-stage solution consisting of a set of m planned vehicle routes is first constructed. The realizations of the random variables are then revealed. Whenever failure occurs, a recourse action generating an extra cost is implemented. A common recourse policy is the following: if the vehicle capacity becomes exceeded on the planned route, the vehicle fills itself to capacity, returns to the depot to unload, and then returns to the last visited vertex; if for any vertex, the vehicle capacity becomes exactly attained, the vehicle returns to the depot and then proceeds to the next vertex along its route. The objective of problem is to minimize the sum of the cost of the first-stage solution and of the expected cost of recourse. The CVRPSD consists of designing m first-stage vehicle routes such that (i) each route starts and ends at the depot, (ii) each vertex is visited once by one vehicle, (iii) if the vehicle capacity is reached at a vertex, a recourse action is applied, and (iv) the objective function is minimized. The earliest recorded contribution to the CVRPSD is due to Tillman [13] who considered a multi-depot variant of the VRP with Poisson distributed demands. The model considered a cost Contents lists available at ScienceDirect journal homepage: www.elsevier.com/locate/caor Computers & Operations Research 0305-0548/$ – see front matter & 2011 Elsevier Ltd. All rights reserved. doi:10.1016/j.cor.2011.02.007 Corresponding author at: Canada Research Chair in Distribution Management, HEC Montreal, 3000 chemin de la Cote-Sainte-Catherine, Montreal, ˆ Canada H3T 2A7. E-mail address: gilbert.laporte@cirrelt.ca (G. Laporte). Computers & Operations Research 38 (2011) 1775–۱۷۸۳ trade-off between exceeding the vehicle capacity and finishing the route with excess capacity. The solution approach was a modification of the Clarke and Wright [14] savings algorithm. A major contribution to the CVRPSD is Bertsimas’s thesis [15] which derived several bounds, as well as asymptotic and theoretical properties. In Laporte et al. [2] more general demand distributions were considered and the depot location was also a decision variable. Exact branch and cut algorithms were presented for the chance constrained version of the problem. Bertsimas [4] gave detailed analytical evidence that the a priori and reoptimization strategies are very similar, and that a priori optimization is a competitive and practical alternative to re-optimization. Laporte and Louveaux [5] developed a generic integer L-shaped method for stochastic programs with recourse. This branch and cut algorithm adds feasibility cuts to a relaxed flow formulation of the problem until an integer feasible solution is found. A tabu search heuristic provided by Gendreau et al. [7] was used to solve a stochastic vehicle routing problem where customers are present with some probability and have random demands. Gendreau et al. [6] also used an integer L-Shaped algorithm for the recourse model of the CVRPSD where the penalty function is the cost of back and forth trips to the depot due to route failures. The survey by Dror et al. [16] emphasizes the effect on a variety of operating and service policies, properties and models for the CVRPSD. More recently, Secomandi [17] solved the CVRPSD using two approximate algorithms: optimistic approximate policy iteration and a one-step rollout algorithm. Yang et al. [18] proposed a dynamic programming recursive objective function for the CVRPSD and the Or-opt operator was adapted to the stochastic case using a fast approximation computation. Laporte et al. [8] developed an improved integer L-shaped algorithm for the CVRPSD with Poisson and normal demands. Haugland et al. [19] considered the design of vehicle districts for the CVRPSD. Tabu search and multi-start heuristics for the problem were developed and compared. Tan et al. [9] studied a multi-objective and multi-model type of CVRPSD, and presented a multi-objective evolutionary algorithm that incorporated two VRPSD-specific heuristics for local exploration and a route simulation method to evaluate the fitness of solutions. Secomandi and Margot [12] proposed a partial re-optimization solution methodology for the CVRPSD. Mendoza et al. [10] provided a memetic algorithm combining genetic operators and local search procedures for a multi-compartment CVRPSD. Finally, Rei et al. [20] have combined Monte Carlo sampling and local branching to the solution of the single-vehicle routing problem with stochastic demands. A survey of stochastic vehicle routing can be found in Cordeau et al. [21]. In the CVRPSDTW, each vertex has an associated time window [ai ,bi ] in which service must start. The time window of the depot is given by [a0,b0]. The inclusion of time windows in the CVRPSD means that in the event of route failure, the time windows of the remaining customers on the planned route may be violated because of the time required by the vehicle to return to the depot and resume its collections. In such a situation, the affected customers are visited separately by special services, which will generate an extra cost. To our knowledge, the available related literature on the CVRPSDTW is limited to two papers. Ong et al. [22] have used a chance constrained model to solve a vehicle routing and scheduling problem with time windows and stochastic demands. A selection criterion was suggested and a sequential heuristic was proposed. Chang [23] applied a stochastic recourse model to a vehicle routing problem with time windows and stochastic demands in which the computation of the expected recourse cost is an extension of that of Gendreau et al. [6] and different from ours. The integer L-shaped method was applied to develop a heuristic for the problem. This heuristic was only tested on Solomon’s C101 instance [24] excluding the vertex demands and the vehicle capacity, and vertices were arbitrarily assigned one of the three demand types in approximately equal proportions. Because Ong et al. [22] and Chang [23] do not solve the same problem as we do, direct comparisons with their algorithms cannot be made. Our aim is to develop an adaptive large neighborhood search metaheuristic for the CVRPSDTW, a methodology that has proved highly successful on other routing problems [25,26]. The remainder of the paper is organized as follows. In Section 2, we provide the detailed computation of the expected cost of solution. The heuristic is described in Section 3, followed by computational results in Section 4, and by conclusions in Section 5.