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

Solving the Single Vehicle Routing Problem with Variable Capacity

TRANSPORTATION SCIENCE 2016年第2期50卷 708-719页

作者： Louveaux, Francois V. Salazar-Gonzalez, Juan-Jose Univ Namur Dept Business Adm B-5000 Namur Belgium Univ La Laguna DEIOC Tenerife 38271 Spain

This paper considers the classical vehicle routing problem (VRP) where the vehicle capacity is not fixed. Indeed, at the moment of acquiring (or renting) the vehicle that will serve all customers, there is some freedom of choice. A larger vehicle capacity implies a lower total distance travelled but larger operating costs. The reverse is true for a smaller vehicle. This paper gives an approach to select the best capacity and the best route to minimize a function of the acquisition cost and travelled distance. We first consider an enumerative approach, which consists of solving a sequence of VRPs, starting from the one having the largest capacity. The number of VRPs to solve using this approach is unknown. Based on computational experiments, this number is mostly large in our benchmark instances. We then proceed to a direct approach based on the two-index formulation of the VRP. We introduce several valid inequalities that allow us to have an integer linear programming formulation of the VRP with fixed vehicle capacity. We describe separation procedures for these inequalities. We conclude with computational results that confirm the utility of these inequalities when solving benchmark VRP instances.

关键词： vehicle routing problem unknown vehicle capacity branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The green vehicle routing problem: A heuristic based exact solution approach

引用

APPLIED SOFT COMPUTING 2016年 39卷 154-164页

作者： Koc, Cagri Karaoglan, Ismail HEC Montreal CIRRELT Montreal PQ Canada HEC Montreal Canada Res Chair Distribut Management Montreal PQ Canada Selcuk Univ Dept Ind Engn Konya Turkey

This paper develops a simulated annealing heuristic based exact solution approach to solve the green vehicle routing problem (G-VRP) which extends the classical vehicle routing problem by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. The problem particularly arises for companies and agencies that employ a fleet of alternative energy powered vehicles on transportation systems for urban areas or for goods distribution. Exact algorithm is based on the branch-and-cut algorithm which combines several valid inequalities derived from the literature to improve lower bounds and introduces a heuristic algorithm based on simulated annealing to obtain upper bounds. Solution approach is evaluated in terms of the number of test instances solved to optimality, bound quality and computation time to reach the best solution of the various test problems. Computational results show that 22 of 40 instances with 20 customers can be solved optimally within reasonable computation time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： The green vehicle routing problem Mixed integer programming formulation branch-and-cut algorithm Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

A multi-stage stochastic integer programming approach for a multi-echelon lot-sizing problem with returns and lost sales

引用

COMPUTERS & OPERATIONS RESEARCH 2020年 116卷

作者： Quezada, Franco Gicquel, Celine Kedad-Sidhoum, Safia Dong Quan Vu Sorbonne Univ CNRS Lab Informat Paris 6 F-75005 Paris France Univ Paris Saclay LRI F-91190 Gif Sur Yvette France CEDRIC CNAM F-75003 Paris France Nokia Paris Saclay Nokia Bell Labs Route Villejust F-91620 Nozay France

We consider an uncapacitated multi-item multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We consider a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We propose a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and develop a branch-and-cut algorithm in order to solve the resulting mixed-integer linear program to optimality. This algorithm relies on a new set of tree inequalities obtained by combining valid inequalities previously known for each individual scenario of the scenario tree. These inequalities are used within a cutting-plane generation procedure based on a heuristic resolution of the corresponding separation problem. Computational experiments carried out on randomly generated instances show that the proposed branch-and-cut algorithm performs well as compared to the use of a stand-alone mathematical solver. Finally, rolling horizon simulations are carried out to assess the practical performance of the multi-stage stochastic planning model with respect to a deterministic model and a two-stage stochastic planning model. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Stochastic lot-sizing Remanufacturing system Lost sales Multi-stage stochastic integer programming Scenario tree Valid inequalities branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Multi-Objective Trip Planning With Solution Ranking Based on User Preference and Restaurant Selection

引用

IEEE ACCESS 2022年 10卷 10688-10705页

作者： Choachaicharoenkul, Supoj Coit, David Wattanapongsakorn, Naruemon King Mongkuts Univ Technol Thonburi Fac Engn Dept Comp Engn Bangkok 10140 Thailand Rutgers State Univ Dept Ind & Syst Engn Piscataway NJ 08854 USA Tsinghua Univ Dept Ind Engn Beijing 100190 Peoples R China

The tourist trip design problem (TTDP) helps the trip planners, such as tourists, tour companies, and government agencies, automate their trip planning. TTDP solver chooses and sequences an optimal subset of point of interest (POIs), which adhere to the POIs attributes and tourist preferences, and then generates a travel itinerary that maximizes their pleasure. However, the traditional TTDP does not include the lunch period at a local restaurant, which causes the rest of the itinerary in the afternoon to shift, nor compulsory POIs that the trip planners must be included in the itinerary. Moreover, as tourism contributes to high greenhouse gas emissions, especially from its transportation, minimizing the itinerary's total distance is also considered. Unfortunately, this objective conflicts with the profit scores;no single itinerary can optimize both objectives simultaneously. Hence, the multi-objective technique and the results of non-dominated itineraries can be organized as a Pareto front. The trip planners can choose one suitable itinerary from the Pareto front based on their preferences. To address these real-world issues, we formulate a new variant of the well-known orienteering problem with time windows (OPTW) called the multi-objective orienteering problem with Time Windows, Restaurant Selection, and Compulsory POIs (MOPTW-RSCP). The proposed problem is provided with a mathematical formulation and two exact algorithms for solving them, i.e., greedy and branch-and-cut Pareto-based techniques. The algorithms' performance is tested against the Rattanakosin island (the old city of Bangkok) dataset. We conduct 24 test cases, and the computational results confirm the algorithms' efficiency.

关键词： Transportation Optimization Legged locomotion Carbon dioxide Tourism industry Mathematical models Planning branch-and-cut algorithm decision support system greedy algorithm multi-objective optimization orienteering problem solution ranking tourist trip design problem

来源：评论

学校读者我要写书评

暂无评论

Evaluation of Environmental Benefits Caused by Reservation-Based Shared Parking: A Case Study of Beijing, China

引用

IEEE ACCESS 2021年 9卷 3744-3751页

作者： Zhao, Pengfei Guan, Hongzhi Wang, Pengfei Yan, Hai Beijing Univ Civil Engn & Architecture Sch Civil & Transportat Engn Beijing 102616 Peoples R China Beijing Univ Technol Fac Urban Construct Coll Architecture & Civil Engn Beijing 100124 Peoples R China Beijing Univ Technol Minist Educ Key Lab Urban Secur & Disaster Engn Beijing 100124 Peoples R China Hebei Normal Univ Sci & Technol Coll Urban Construct Qinhuangdao 066004 Hebei Peoples R China Beijing Univ Technol Fac Urban Construct Coll Metropolitan Transportat Beijing 100124 Peoples R China

With the help of accurate parking navigation systems, sharing vacant private parking spaces with public travelers may have the potential of reducing the number of cruising vehicles and contribute to traffic emission reduction. However, the quantitative effects of such a measure are still relatively unknown in traffic management. In this article, we firstly established an optimal allocation model of shared parking spaces, which is a pure integer linear programming model of maximizing the number of served public vehicles to avoid cruising for parking. Further, the parking space allocation model was expanded to an estimation model that quantifies the effect of emission reduction. Secondly, a branch-and-cut algorithm was introduced as the core algorithm to solve the proposed models. Finally, detailed sensitivity analysis, based on empirical data collected by electronic parking toll collections and questionnaire surveys in Beijing, China, evaluated the proposed model and algorithm. The results indicate that shared parking can not only effectively reduce the cruising time and the number of vehicles, but also has significantly a positive effect on emission reduction. This research is helpful to provide theoretical support for alleviating parking pressure and environmental problems.

关键词： Potential emission reduction shared parking optimal parking space allocation pure integer linear programming model branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The Shared Customer Collaboration Vehicle Routing Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期265卷 1078-1093页

作者： Fernandez, Elena Roca-Riu, Mireia Speranza, M. Grazia Barcelona Tech UPC Dept Stat & Operat Res Carrer Jordi Girona1C5-208 Barcelona 08034 Spain Barcelona Grad Sch Math BGSMath Edifici C Bellaterra 08193 Spain Swiss Fed Inst Technol Zurich ETHZ Inst Transport Planning & Syst Stefano Franscini Pl 5HIL F 34-2 Zurich Switzerland Univ Brescia Dipartimento Metodi Quantitat Contrada Santa Chiara 50 I-25122 Brescia Italy

This paper introduces a new vehicle routing problem that arises in an urban area where several carriers operate and some of their customers have demand of service for more than one carrier. The problem, called Shared Customer Collaboration Vehicle Routing Problem, aims at reducing the overall operational cost in a collaboration framework among the carriers for the service of the shared customers. Alternative mathematical programming formulations are proposed for the problem that are solved with a branch-and-cut algorithm. Computational experiments on different sets of benchmark instances are run to assess the effectiveness of the formulations. Moreover, in order to estimate the savings coming from the collaboration, the optimal solutions are compared with the solutions obtained when carriers work independently from each other. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Vehicle routing problem Carriers collaboration Mixed integer programming branch-and-cut algorithm Urban logistics

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Cluster Editing: Evaluation and Experiments

引用

algorithmICA 2011年第2期60卷 316-334页

作者： Boecker, Sebastian Briesemeister, Sebastian Klau, Gunnar W. Univ Jena Inst Informat Jena Germany Jena Ctr Bioinformat Jena Germany Univ Tubingen Div Simulat Biol Syst ZBIT WSI Tubingen Germany CWI NL-1090 GB Amsterdam Netherlands

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of vertical bar V vertical bar , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k <= 25 vertical bar V vertical bar In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments" in the Proceedings of the 7th Workshop on Experimental algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.).

关键词： Cluster editing algorithm engineering Computer experiments NP-complete problem Fixed-parameter tractability FPT Integer linear programming ILP branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The inventory routing problem with split deliveries

引用

NETWORKS 2023年第4期82卷 400-413页

作者： Dinh, Nho Minh Archetti, Claudia Bertazzi, Luca Univ Brescia Dept Econ & Management Brescia Italy ESSEC Business Sch Dept Informat Syst Decis Sci & Stat Paris France

We study the benefit of introducing split deliveries in the inventory routing problem (IRP), both when the order-up-to level (OU) and the maximum level replenishment policies are applied. We first propose a mathematical formulation and solve it by implementing a branch-and-cut algorithm. Then, we carry out a worst-case analysis to show the cost increase we have in the worst case by using unsplit deliveries instead of split deliveries, both for the OU and the maximum-level replenishment policies. Extensive computational results on benchmark instances allow us to evaluate the benefit of introducing split deliveries. Finally, a sensitivity analysis on customer demands, initial inventory levels, maximum inventory levels and distance to the depot allows us to understand the instance features that make split deliveries effective in IRPs.

关键词： branch-and-cut algorithm inventory routing problems maximum-level order-up-to-level split deliveries worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

The Multiple Steiner TSP with order constraints: complexity and optimization algorithms

引用

SOFT COMPUTING 2020年第23期24卷 17957-17968页

作者： Gabrel, Virginie Mahjoub, A. Ridha Taktak, Raouia Uchoa, Eduardo PSL Res Univ Univ Paris Dauphine CNRS LAMSADE F-75016 Paris France Univ Sfax CRNS ISIMS Sfax Tunisia Univ Sfax CRNS LT2S Sfax Tunisia Univ Fed Fluminense Dept Engn Prod Niteroi RJ Brazil

We consider a variant of the Travelling Salesman Problem (TSP), the Multiple Steiner TSP with Order constraints (MSTSPO). Consider a weighted undirected graph and a set of salesmen, and each salesman is associated with a set of compulsory vertices to visit, called terminals. The MSTSPO consists in finding a minimum-cost subgraph containing for each salesman a tour going in a specified order through its terminals. Along with its importance from a theoretical point of view, the problem is also challenging in practice since it has applications in telecommunication networks. We show that the problem is NP-hard even for a single salesman and propose integer programming formulations. We then devise both branch-and-cut and branch-and-Price algorithms to solve the problem. The extensive computational results are presented, showing the efficiency of our algorithms.

关键词： Steiner TSP Order constraints Integer linear programming branch-and-Price algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving VLSI design and DNA sequencing problems using bipartization of graphs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第2期51卷 749-781页

作者： Fouilhoux, Pierre Mahjoub, A. Ridha Univ Paris 09 LAMSADE CNRS F-75775 Paris 16 France Univ Paris 06 Lab LIP6 CNRS UMR 7626 F-75005 Paris France

In this paper we consider the 2-layer constrained via minimization problem and the SNP haplotype assembly problem. The former problem arises in the design of integrated and printed circuit boards, and the latter comes up in the DNA sequencing process for diploid organisms. We show that, for any maximum junction degree, the problem can be reduced to the maximum bipartite induced subgraph problem. Moreover we show that the SNP haplotype assembly problem can also be reduced to the maximum bipartite induced subgraph problem for the so-called minimum error correction criterion. We give a partial characterization of the bipartite induced subgraph polytope. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm has been used to solve real and large instances.

关键词： Electronics Genomics Bipartite induced subgraph problem Polyhedral approach branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：