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

An integer l-shaped algorithm for the vehicle routing problem with time windows and stochastic demands

EUROPEAN JOURNAl OF OPERATIONAl RESEARCH 2023年第2期308卷 676-695页

作者： De la Vega, Jonathan Gendreau, Michel Morabito, Reinaldo Munari, Pedro Ordonez, Fernando Univ Fed Sao Carlos Prod Engn Dept Rodovia Washington LuisKm 235 BR-13565905 Sao Carlos SP Brazil SimpliRoute Holanda 100 Santiago 7510021 Chile Polytech Montreal Ctr Interuniv Rech Reseaux Entreprise Logist & Tra 2500 Chemin Polytech Montreal PQ H3C 3A7 Canada Polytech Montreal Dept Math & Genie Ind 2500 Chemin Polytech Montreal PQ H3C 3A7 Canada Univ Chile Dept Ingn Ind Republ 701 Santiago 8370439 Chile

This paper addresses the vehicle routing problem with time windows and stochastic demands (VRPTWSD). The problem is modeled as a two-stage stochastic program with recourse, in which routes are designed in the first stage and executed in the second. A failure occurs if the load of the vehicle is insufficient to meet the observed demand of a customer, implying recourse actions to recover feasibility. We consider the classical recourse policy where reactive trips to the depot are made in case of failures and a fixed rule-based recourse policy where, in addition, preventive trips are allowed. These recourse actions delay the vehicle and may cause further failures if the arrival times on the remaining customers of the planned route do not satisfy their time windows. An additional recourse action is used to service the customers whose time windows would be violated in the planned routes. We propose an integer l-shaped algorithm considering the mentioned recourse actions. To the best of our knowledge, this is the first tailored exact approach for the VRPTWSD. Computational experiments using 112 benchmark in-stances evaluate the performance of this algorithm as well as the quality of the stochastic problem solu-tions. The results indicate significant savings in the solutions when using the fixed rule-based policy and round-trip recourse actions instead of the classical policy. Additionally, the algorithm performed better with the fixed rule-based policy, solving to optimality all instances with up to 34 customers, and taking less time on instances that were solved to optimality with both policies.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Routing Time windows Stochastic demand integer l-shaped algorithm Fixed rule-based policy

来源：评论

学校读者我要写书评

暂无评论

An integer l-shaped algorithm for vehicle routing problem with simultaneous delivery and stochastic pickup

引用

COMPUTERS & OPERATIONS RESEARCH 2023年 154卷

作者： Che, Yuxin Zhang, Zhenzhen Natl Univ Singapore Dept Ind Syst Engn & Management Singapore Singapore Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China

This paper addresses an exact algorithm for vehicle routing problem with simultaneous pickup and delivery in which customer demands to be collected are stochastic. The problem is modeled as a two-stage stochastic programming problem with recourse, in which routing decisions are made based on known delivery demand and deterministic expected pickup demand in the first stage and recourse actions are made in the second stage when stochastic pickup quantities have been revealed. However, failures happen when the load of the vehicle is insufficient to meet the observed pickup demand of a customer. Three recourse policies are proposed to help deal with the failures to proceed with the routing decisions in the first stage. The integer l-shaped algorithmic framework is used to solve this two-stage stochastic programming problems with recourse. Furthermore, effective lower bounding of the expected recourse cost of partial routes is designed for the three recourse policies, respectively. Computational experiments on the newly generated instances compare the performance of the integer l-shaped algorithm under the three recourse policies, and the conclusion is validated via numerous simulations. The effectiveness of the proposed lower bounding functionals is confirmed through reduced optimality gaps and lower computing times.

关键词： Routing Simultaneous delivery and stochastic pickup Stochastic programming integer l-shaped algorithm Recourse policy

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy

引用

EUROPEAN JOURNAl OF OPERATIONAl RESEARCH 2019年第1期273卷 175-189页

作者： Salavati-Khoshghalb, Majid Gendreau, Michel Jabali, Ola Rei, Walter CIRRELT CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada Univ Montreal Dept Informat & Rech Operat CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada Polytech Montreal Dept Math & Genie Ind CP 6079Succ Ctr Ville Montreal PQ H3C 3J7 Canada Politecn Milan Dipartimento Elettron Informaz & Bioingn Piazza Leonardo da Vinci 32 I-20133 Milan Italy Univ Quebec Montreal Dept Management & Technol Ecole Sci Gest CP 8888Succ Ctr Ville Montreal PQ H3C 3P8 Canada

This paper examines the Vehicle Routing Problem with Stochastic Demands (VRPSD), in which the actual demand of customers can only be realized upon arriving at the customer location. Under demand uncertainty, a planned route may fail at a specific customer when the observed demand exceeds the residual capacity. There are two ways to face such failure events, a vehicle can either execute a return trip to the depot at the failure location and refill the capacity and complete the split service, or in anticipation of potential failures perform a preventive return to the depot whenever the residual capacity falls below a threshold;overall, these return trips are called recourse actions. In the context of VRPSD, a recourse policy which schedules various recourse actions based on the visits planned beforehand on the route must be designed. An optimal recourse policy prescribes the cost-effective returns based on a set of optimal customer-specific thresholds. We propose an exact solution method to solve the multi-VRPSD under an optimal restocking policy. The integer l-shaped algorithm is adapted to solve the VRPSD in a branch-and-cut framework. To enhance the efficiency of the presented algorithm, several lower bounding schemes are developed to approximate the expected recourse cost. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Routing Stochastic demands Optimal restocking policy integer l-shaped algorithm lower bounding functionals

来源：评论

学校读者我要写书评

暂无评论

A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands

引用

TRANSPORTATION SCIENCE 2019年第5期53卷 1334-1353页

作者： Salavati-Khoshghalb, Majid Gendreau, Michel Jabali, Ola Rei, Walter Univ Montreal Dept Informat & Rech Operat Montreal PQ H3C 3J7 Canada Ctr Interuniv Rech Reseaux Entreprise Logist & Tr Montreal PQ H3C 3J7 Canada Polytech Montreal Dept Math & Genie Ind Montreal PQ H3C 3J7 Canada Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy Univ Quebec Montreal Dept Management & Technol Ecole Sci Gest Montreal PQ H3C 3P8 Canada

In this paper we consider the vehicle routing problem with stochastic demands (VRPSD). We consider that customer demands are only revealed when a vehicle arrives at customer locations. Failures occur whenever the residual capacity of the vehicle is insufficient to serve the observed demand of a customer. Such failures entail that recourse actions be taken to recover route feasibility. These recourse actions usually take the form of return trips to the depot, which can be either done in a reactive or proactive fashion. Over the years, there have been various policies defined to perform these recourse actions in either a static or a dynamic setting. In the present paper, we propose policies that better reflect the fixed operational rules that can be observed in practice and that also enable implementing preventive recourse actions. We define the considered operational rules and show how, for a planned route, these operational rules can be implemented using a fixed threshold-based policy to govern the recourse actions. An exact solution algorithm is developed to solve the VRPSD under the considered policies. Finally, we conduct an extensive computational study, which shows that significantly better solutions can be obtained when using the proposed policies compared with solving the problem under the classic recourse definition.

关键词： threshold-based recourse policies operational rules vehicle routing problem with stochastic demands partial route integer l-shaped algorithm lower bounding functionals

来源：评论

学校读者我要写书评

暂无评论

Incorporating Wind Energy in Power System Restoration Planning

引用

IEEE TRANSACTIONS ON SMART GRID 2019年第1期10卷 16-28页

作者： Golshani, Amir Sun, Wei Zhou, Qun Zheng, Qipeng P. Hou, Yunhe Univ Cent Florida Dept Elect & Comp Engn Orlando FL 32816 USA Univ Cent Florida Dept Ind Engn & Management Syst Orlando FL 32816 USA Univ Hong Kong Elect & Elect Engn Dept Hong Kong Peoples R China

Wind energy is rapidly growing. While wind brings us clean and inexpensive energy, its inherent variability and uncertainty present challenges for the power grid. In particular, employing wind energy for power system restoration is very challenging. A fast and reliable restoration plays a vital role to achieve the self-healing power grid. This paper develops a novel offline restoration planning tool for harnessing wind energy to enhance grid resilience. The wind-for-restoration problem is formulated as a stochastic mixed-integer linear programming problem with generated wind energy scenarios. The problem is then decomposed into two stages and solved with the integer l-shaped algorithm. Numerical experiments have been conducted through different case studies using the modified IEEE 57-bus system. The developed tool can provide the scheduled wind power at each restoration time. The impact of wind energy is investigated from the aspects of location and inertia capability, as well as wind penetration, fluctuation, and uncertainty. Moreover, a dynamic response validation tool is developed to validate the results of optimization problem in a dynamic simulation software. Simulation results demonstrate that the optimal wind harnessing strategy can help improve system restoration process and enhance system resilience.

关键词： integer l-shaped algorithm mixed-integer linear programming power system restoration stochastic optimization wind uncertainty

来源：评论

学校读者我要写书评

暂无评论

An integer l-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays

引用

DISCRETE APPlIED MATHEMATICS 2011年第9期159卷 883-895页

作者： Heilporn, Geraldine Cordeau, Jean-Francois laporte, Gilbert HEC Montreal Canada Res Chair Distribut Management Montreal PQ H3T 2A7 Canada HEC Montreal CIRRELT Montreal PQ H3T 2A7 Canada HEC Montreal Canada Res Chair Logist & Transportat Montreal PQ H3T 2A7 Canada

This paper considers a single-vehicle Dial-a-Ride Problem in which customers may experience stochastic delays at their pickup locations. If a customer is absent when the vehicle serves the pickup location, the request is fulfilled by an alternative service (e.g., a taxi) whose cost is added to the total cost of the tour. In this case, the vehicle skips the corresponding delivery location, which yields a reduction in the total tour cost. The aim of the problem is to determine an a priori Hamiltonian tour minimizing the expected cost of the solution. This problem is solved by means of an integer l-shaped algorithm. Computational experiments show that the algorithm yields optimal solutions on several instances within reasonable CPU times. It is also shown that the actual cost of an optimal solution obtained with this algorithm can be significantly smaller than that of an optimal solution obtained with a deterministic formulation. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Dial-a-Ride Problem Stochastic programming integer l-shaped algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-Stage Adaptive Restoration Decision Support System for a Self-Healing Power Grid

引用

IEEE TRANSACTIONS ON INDUSTRIAl INFORMATICS 2017年第6期13卷 2802-2812页

作者： Golshani, Amir Sun, Wei Zhou, Qun Zheng, Qipeng P. Tong, Jianzhong Univ Cent Florida Dept Elect & Comp Engn Orlando FL 32816 USA Univ Cent Florida Dept Ind Engn & Management Syst Orlando FL 32816 USA PJM Interconnect LLC Audubon PA 19403 USA

Power outages cost American industries and businesses billions of dollars and jeopardize the lives of hospital patients. The losses can be greatly reduced with a fast, reliable, and flexible self-healing tool. This paper is aimed to tackle the challenging task of developing an adaptive restoration decision support system (RDSS). The proposed RDSS determines restoration actions both in planning and real-time phases and adapts to constantly changing system conditions. The comprehensive formulation encompasses practical constraints including ac power flow, dynamic reserve, and load modeling. The combinatorial problem is decomposed into a two-stage formulation solved by an integer l-shaped algorithm. The two stages are then executed online in the RDSS framework employing a sliding window method. The IEEE 39-bus system has been studied under normal and contingency conditions to demonstrate the effectiveness and efficiency of the proposed online RDSS.

关键词： Adaptive restoration dynamic reserve integer l-shaped algorithm mixed-integer linear programming two-stage optimization

来源：评论

学校读者我要写书评

暂无评论

Partial-route inequalities for the multi-vehicle routing problem with stochastic demands

引用

DISCRETE APPlIED MATHEMATICS 2014年 177卷 121-136页

作者： Jabali, Ola Rei, Walter Gendreau, Michel laporte, Gilbert C1RRELT & HEC Montreal Montreal PQ H3C 3J7 Canada Univ Quebec CIRRELT Montreal PQ H2X 3X2 Canada Univ Quebec Dept Management & Technol Montreal PQ H2X 3X2 Canada Ecole Polytech C1RRELT Montreal PQ H3C 3J7 Canada Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 3J7 Canada

This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer l-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Stochastic vehicle routing problem Stochastic demand Stochastic programming integer l-shaped algorithm General partial routes lower bounding functionals

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：