检索结果-内蒙古大学图书馆

Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem

TRANSPORTATION SCIENCE 2015年第2期49卷 335-354页

作者： Gschwind, Timo Irnich, Stefan Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ D-55128 Mainz Germany

A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypical vehicle-routing problem with ordinary and dynamic time windows. For the first time (to our knowledge), both ordinary and dynamic time windows are handled in the column-generation subproblem. For the solution, an effective column-generation pricing procedure is derived that allows fast shortest-path computations due to new dominance rules. The new approach is compared with alternative column-generation algorithms that handle dynamic time windows either as constraints of the master program or with less effective labeling procedures. Computational experiments indicate the superiority of the new approach.

关键词： transportation vehicle routing dynamic time windows dial-a-ride problem labeling algorithm ride-time constraints time synchronization branch-and-price

来源：评论

学校读者我要写书评

暂无评论

Advanced sensitivity analysis of the fuzzy assignment problem

引用

APPLIED SOFT COMPUTING 2011年第8期11卷 5341-5349页

作者： Lin, Chi-Jen Wen, Ue-Pyng Lin, Pei-Yi Ta Hwa Inst Technol Dept Ind Engn & Management Hsinchu Taiwan Natl Tsing Hua Univ Dept Ind Engn & Engn Management Hsinchu Taiwan

This paper concentrates on sensitivity analysis of the fuzzy assignment problem (FAP). Since most real environments are uncertain, the FAP is more realistic than the assignment problem in application. Owing to the high degeneracy of the FAP, as that of the assignment problem, traditional sensitivity analysis, called Type I sensitivity analysis, which determines the range in which the current optimal basis remains optimal, is impractical. Hence, we attempt to perform other two types of advanced sensitivity analysis, called Type II and Type III sensitivity analysis, to overcome this problem. A labeling algorithm is then presented, where Type II sensitivity analysis is to determine the range of perturbation to keep the current optimal assignment remaining optimal, and Type III sensitivity analysis is to determine the range for which the rate of change of optimal value function remains unchanged. The procedure of the labeling algorithm is divided into two parts: one is when the unassigned cell is perturbed, and the other is when the assigned cell is perturbed. An example is presented to demonstrate that the labeling algorithm is a useful tool for determining the Type II and Type III sensitivity analysis of the FAP. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Assignment problem Fuzzy theory Sensitivity analysis Degeneracy labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A Branch-Price-and-Cut algorithm for the Inventory-Routing Problem

引用

TRANSPORTATION SCIENCE 2016年第3期50卷 1060-1076页

作者： Desaulniers, Guy Rakke, Jorgen G. Coelho, Leandro C. Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 2A7 Canada Gerad Montreal PQ H3C 2A7 Canada Norwegian Univ Sci & Technol Dept Marine Technol N-7491 Trondheim Norway Univ Laval Fac Sci Adm Quebec City PQ G1V 0A6 Canada CIRRELT Quebec City PQ G1V 0A6 Canada

The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to service over a multiperiod horizon, the IRP consists of determining when to visit each customer, which quantity to deliver in each visit, and how to combine the visits in each period into feasible routes such that the total routing and inventory costs are minimized. In this paper, we propose an innovative mathematical formulation for the IRP and develop a state-of-the-art branch-price-and-cut algorithm for solving it. This algorithm incorporates known and new families of valid inequalities, including an adaptation of the well-known capacity inequalities, as well as an ad hoc labeling algorithm for solving the column generation subproblems. Through extensive computational experiments on a widely used set of 640 benchmark instances involving between two and five vehicles, we show that our branch-price-and-cut algorithm clearly outperforms a state-of-the-art branch-and-cut algorithm on the instances with four and five vehicles. In this instance set, 238 were still open before this work and we proved optimality for 54 of them.

关键词： inventory routing branch price and cut capacity inequalities labeling algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期247卷 60-71页

作者： Gschwind, Timo Johannes Gutenberg Univ Mainz Chair Logist Management D-55128 Mainz Germany

In the Synchronized Pickup and Delivery Problem (SPDP), user-specified transportation requests from origin to destination points have to be serviced by a fleet of homogeneous vehicles. The task is to find a set of minimum-cost routes satisfying pairing and precedence, capacities, and time windows. Additionally, temporal synchronization constraints couple the service times at the pickup and delivery locations of the customer requests in the following way: a request has to be delivered within prespecified minimum and maximum time lags (called ride times) after it has been picked up. The presence of these ride-time constraints severely complicates the subproblem of the natural column-generation formulation of the SPDP so that it is not clear if their integration into the subproblem pays off in an integer column-generation approach. Therefore, we develop four branch-and-cut-and-price algorithms for the SPDP based on column-generation formulations that use different subproblems. Two of these subproblems are considered for the first time in this paper have not been studied before. We derive new dominance rules and labeling algorithms for their effective solution. Extensive computational results indicate that integrating either both types of ride-time constraints or only the maximum ride-time constraints into the subproblem results in the strongest overall approach. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Vehicle routing Pickup and delivery Temporal synchronization labeling algorithm Branch-and-cut-and-price

来源：评论

学校读者我要写书评

暂无评论

The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2014年第Feb.期62卷 1-22页

作者： Bhusiri, Narath Qureshi, Ali Gul Taniguchi, Eiichi Kyoto Univ Dept Urban Management Nishikyo Ku Kyoto 6158540 Japan

This paper introduces the vehicle routing problem with soft time windows (VRPSTW) in which problem definition differs from ones previously defined in literature. Branch-and-price approach is employed, resulting in a set partitioning master problem and its new subproblem. Novel techniques are consequently developed to solve this new subproblem. Experimental results report the comparisons of these solution techniques under the branch-and-price framework. The VRPSTW solutions have further been compared to the state-of-the-art literature, signifying the superiority of the VRPSTW on this issue. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Freight transport Vehicle routing Soft time window Column generation labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

frvcpy: An Open-Source Solver for the Fixed Route Vehicle Charging Problem

引用

INFORMS JOURNAL ON COMPUTING 2021年第4期33卷 1277-1283页

作者： Kullman, Nicholas D. Froger, Aurelien Mendoza, Jorge E. Goodson, Justin C. Univ Tours Lab Fundamental & Appl Comp Sci LIFAT F-37200 Tours France Univ Bordeaux Inst Math Bordeaux Inria Bordeaux Sud Ouest F-33405 Talence France HEC Montreal Montreal PQ H3T 2A7 Canada Ctr Interuniv Rech Sur Reseaux Entreprise Logist Montreal PQ H3T 1J4 Canada St Louis Univ Richard A Chaifetz Sch Business St Louis MO 63103 USA

Electric vehicles offer a pathway to more sustainable transportation, but their adoption entails new challenges not faced by their petroleum-based counterparts. A difficult task in vehicle routing problems addressing these challenges is determining how to make good charging decisions for an electric vehicle traveling a given route. This is known as the fixed route vehicle charging problem. An exact and efficient algorithm for this task exists, but its implementation is sufficiently complex to deter researchers from adopting it. In this work we introduce frvcpy, an open-source Python package implementing this algorithm. Our aim with the package is to make it easier for researchers to solve electric vehicle routing problems, facilitating the development of optimization tools that may ultimately enable the mass adoption of electric vehicles.

关键词： electric vehicles vehicle routing open-source Python exact optimization labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A practical model of routing problems for automated guided vehicles with acceleration and deceleration

引用

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 2014年第5期8卷

作者： Nishi, Tatsushi Matsushita, Susumu Hisano, Takeshi Morikawa, Masahi Osaka Univ Grad Sch Engn Sci Toyonaka Osaka 5608531 Japan Daifuku Co Ltd Shiga 5291662 Japan

We consider an optimization of conflict-free routing problems for automated guided vehicles (AGV) with acceleration and deceleration. A continuous time model is developed to represent the dynamics of vehicles. In the proposed model, the transportation model is discretized into several regions. A network model is created by taking into account the acceleration and deceleration motions. The acceleration and deceleration are represented at curve locations. Column generation heuristic is used to find a near-optimal solution. In this algorithm, we construct a heuristic rule to generate a feasible solution with acceleration and deceleration of vehicles after the column generation. The pricing problem is represented by a resource constrained shortest path problem, which is effectively solved by a labeling algorithm The dominance relation for acceleration and deceleration is addressed. In the proposed model, the dynamics of real speed AGV model are reflected into the routing problems. By comparing the performance of the conventional method, the effectiveness of the proposed method is demonstrated.

关键词： Automated guided vehicle Column generation heuristics Routing labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

Branch-and-price algorithm for the location-routing problem with time windows

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2016年 86卷 1-19页

作者： Ponboon, Sattrawut Qureshi, Ali Gul Taniguchi, Eiichi Kyoto Univ Dept Urban Management Nishikyo Ku Kyoto 6158540 Japan

This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Location-routing problem Time windows Branch-and-price Column generation labeling algorithm Exact solution

来源：评论

学校读者我要写书评

暂无评论

Shortest route computation in distributed systems

引用

COMPUTERS & OPERATIONS RESEARCH 2004年第10期31卷 1621-1633页

作者： Wang, JC Kaempke, T Missouri Western State Coll Dept Business St Joseph MO 64507 USA FAW Res Inst Artificial Intelligence D-89081 Ulm Germany

This paper presents a polynomial time algorithm for computing the shortest route in distributed systems. A distributed system is composed of autonomous subsystems and a central computing server. A subsystem stores and maintains its own data, and is obligated to provide the central computing server with the information about its intersections with other subsystems. The approach presented in this paper is for the central computing server to compute the shortest route that crosses subsystems based on the partial local information provided by the subsystems. It is the first efficient algorithm that guarantees to find the shortest route in such a distributed system. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： distributed computing shortest path problem labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows

引用

OPTIMIZATION LETTERS 2020年第3期14卷 579-609页

作者： Fachini, Ramon Faganello Armentano, Vinicius Amaral Univ Estadual Campinas Fac Engn Eletr & Comp BR-13083852 Campinas SP Brazil

This article proposes extensions of exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows, which are a limited enlargement of the generally referred to as hard time windows. The service of a customer can be started before or after the hard time window at a penalty cost. The addressed problem thus requires the determination of a sequence of customers and their respective service start times in order to minimize the sum of traveling cost with earliness and lateness cost. Computational tests are conducted on a variety of symmetric and asymmetric instances proposed in the literature, and the advantages of flexible windows are stressed.

关键词： Traveling salesman problem Flexible time windows Dynamic programming labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：