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

A modified single-objective genetic algorithm for solving the rural postman problem with load-dependent costs

KNOWLEDGE-BASED SYSTEMS 2025年 312卷

作者： De Santis, David Landete, Mercedes Cabezas, Xavier Sanchis, Jose Maria Peiro, Juanjo Escuela Super Politecn Litoral Fac Ciencias Nat & Matemat Guayaquil Ecuador Univ Miguel Hernandez Ctr Invest Operat Elche Spain Escuela Super Politecn Litoral Ctr Estudios & Invest Estadist Guayaquil Ecuador Univ Politecn Valencia Dept Matemat Aplicada Valencia Spain Univ Valencia Dept Estadist & Invest Operat Fac Ciencies Matemat Valencia Spain

This study addresses the rural postman problem with load-dependent costs, a variant of the arc routing problem where the traversal cost of an edge depends on its length and the vehicle's load. The objective is to find a minimum-cost tour that services all required edges, a problem of particular importance when the demand weight is significant compared to the vehicle's curb weight. We present an integer linear programming model for the problem and propose a heuristic algorithm based on bio-inspired methodologies to efficiently obtain near-optimal solutions within short computing times. The effectiveness of the approach is demonstrated through computational experiments on benchmark instances, and the results highlight the practicality of the proposed methods.

关键词： CPP-LC Genetic algorithm rural postman problem Transportation Logistics

来源：评论

学校读者我要写书评

暂无评论

The rural postman problem with deadline classes

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第3期105卷 390-400页

作者： Letchford, AN Eglese, RW Univ Lancaster Sch Management Dept Management Sci Lancaster LA1 4YX England

Vehicle routing problems with general time windows are extremely difficult to solve. However, the time windows in a particular problem may have a special structure which can be exploited. We consider a single-vehicle are-routing problem in which the arcs are partitioned into deadline classes. It is shown that a cutting-plane approach works well for this problem. (C) 1998 Elsevier Science B.V.

关键词： rural postman problem time windows integer programming cutting-planes

来源：评论

学校读者我要写书评

暂无评论

The directed profitable rural postman problem with incompatibility constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第2期261卷 549-562页

作者： Colombi, Marco Corberan, Angel Mansini, Renata Plana, Isaac Sanchis, Jose M. Univ Brescia Dept Informat Engn Brescia Italy Univ Valencia Dept Stat & Operat Res Burjassot Spain Univ Valencia Dept Math Econ & Business Valencia Spain Univ Politech Valencia Dept Appl Math Valencia Spain

In this paper, we study a variant of the directed rural postman problem (RPP) where profits are associated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers and shippers. We call this problem the directed profitable rural postman problem with incompatibility constraints. We propose two problem formulations and introduce a matheuristic procedure exploiting the presence of a variant of the generalized independent set problem (GISP) and of the directed rural postman problem (DRPP) as subproblems. Computational results show how the matheuristic is effective outperforming in many cases the result obtained in one hour computing time by a straightforward branch-and-cut approach implemented with IBM CPLEX 12.6.2 on instances with up to 500 nodes, 1535 arcs, 1132 profitable arcs, and 10,743 incompatibilities. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Routing rural postman problem Incompatibility constraints Generalized independent set problem

来源：评论

学校读者我要写书评

暂无评论

A heuristic algorithm based on Monte Carlo methods for the rural postman problem

引用

COMPUTERS & OPERATIONS RESEARCH 1998年第12期25卷 1097-1106页

作者： de Cordoba, PF Raffi, LMG Sanchis, JM Univ Politecn Valencia Dept Matemat Aplicada E-46071 Valencia Spain

The rural postman problem (RPP) consists of finding a minimum cost traversal of a specified are subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient. (C) 1998 Published by Elsevier Science Ltd. All rights reserved.

关键词： rural postman problem routing problems Monte Carlo methods

来源：评论

学校读者我要写书评

暂无评论

Modeling and Solving the Intersection Inspection rural postman problem

引用

INFORMS JOURNAL ON COMPUTING 2021年第3期33卷 1245-1257页

作者： Roy, Debdatta Sinha Masone, Adriano Golden, Bruce Wasil, Edward Staples Inc Framingham MA 01702 USA Univ Naples Federico II Dept Elect Engn & Informat Technol I-80125 Naples Italy Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA Amer Univ Kogod Sch Business Washington DC 20016 USA

Local governments inspect roads to decide which segments and intersections to repair. Videos are taken using a camera mounted on a vehicle. The vehicle taking the videos proceeds straight or takes a left turn to cover an intersection fully. We introduce the intersection inspection rural postman problem (IIRPP), which is a new variant of the rural postman problem (RPP) that involves turns. We develop integer programming formulations of the IIRPP based on two different graph transformations to generate least-cost vehicle routes. One formulation is based on a new idea of transforming a graph. A second formulation is based on a graph transformation idea from the literature. Computational experiments show that the formulation involving the new graph transformation idea performs much better than the other formulation. We also develop an RPP-based heuristic and a heuristic based on a modified RPP. Heuristic solutions are improved by solving integer programming formulations on an induced subgraph. Computational experiments show that the heuristics based on the modified RPP perform much better than the RPP-based heuristics. The best-performing heuristic generates very good quality IIRPP-feasible routes on large street networks quickly. Summary of Contribution. Our paper addresses a real-world problem faced by local governments during road inspections. The real-world problem that we solve and the methodologies that we use fall at the intersection of computing and operations research. We introduce the intersection inspection rural postman problem, which is a new variant of the rural postman problem that involves turns to capture this real-world scenario. The rural postman problem is an important problem in vehicle routing. Studying new variants of this problem is key to extending the practice and theory of vehicle routing. We develop an integer programming formulation based on a new idea of transforming a graph and also develop heuristics based on the rural postman problem.

关键词： rural postman problem node routing arc routing integer programming heuristics

来源：评论

学校读者我要写书评

暂无评论

Polyhedral analysis and a new algorithm for the length constrained K-drones rural postman problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2022年第1期83卷 67-109页

作者： Campbell, James Corberan, Angel Plana, Isaac Sanchis, Jose M. Segura, Paula Univ Missouri St Louis MO 63121 USA Univ Valencia Valencia Spain Univ Politecn Valencia Valencia Spain

The Length Constrained K-Drones rural postman problem (LC K-DRPP) is a continuous optimization problem where a set of curved or straight lines of a network have to be traversed, in order to be serviced, by a fleet of homogeneous drones, with total minimum cost. Since the range and endurance of drones is limited, we consider here that the length of each route is constrained to a given limit L. Drones are not restricted to travel on the network, and they can enter and exit a line through any of its points, servicing only a portion of that line. Therefore, shorter solutions are obtained with "aerial" drones than with "ground" vehicles that are restricted to the network. If a LC K-DRPP instance is digitized by approximating each line with a polygonal chain, and it is assumed that drones can only enter and exit a line through the points of the chain, an instance of the Length Constrained K-vehicles rural postman problem (LC K-RPP) is obtained. This is a discrete arc routing problem, and therefore can be solved with combinatorial optimization techniques. However, when the number of points in each polygonal chain is very large, the LC K-RPP instance can be so large that it is very difficult to solve, even for heuristic algorithms. Therefore, it is necessary to implement a procedure that generates smaller LC K-RPP instances by approximating each line by a few but "significant" points and segments. In this paper, we present a new formulation for the LC K-RPP with two binary variables for each edge and each drone representing the first and second traversals of the edge, respectively. We make a polyhedral study of the set of solutions of a relaxed formulation and prove that several families of inequalities induce facets of the polyhedron. We design and implement a branch-and-cut algorithm for the LC K-RPP that incorporates the separation of these inequalities. This B &C is the main routine of an iterative algorithm that, by solving a LC K-RPP instance at each step, finds good

关键词： Drones rural postman problem Length constraints Facets Branch and cut

来源：评论

学校读者我要写书评

暂无评论

Multiple order pick sequencing in a carousel system: A solvable case of the rural postman problem

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1996年第12期47卷 1504-1515页

作者： Vandenberg, JP UNIV TWENTE FAC MECH ENGNPROD OPERAT MANAGEMENT GRPPOB 217NL-7500 AE ENSCHEDENETHERLANDS

We consider the problem of sequencing picks in a set of orders on a single carousel. First we consider the situation in which the sequence of the orders is given. For this problem we present an efficient dynamic programming algorithm. Second, we consider the problem without a given order sequence. We simplify this problem to a rural postman problem on a circle and solve this problem to optimality. Finally, we show that the solution of the rural postman problem requires at most 1.5 revolutions mon than a lower bound of an optimum solution to the original problem.

关键词： dynamic programming production rural postman problem sequencing warehousing

来源：评论

学校读者我要写书评

暂无评论

The rural postman problem with Time Windows

引用

NETWORKS 2014年第3期64卷 169-180页

作者： Monroy-Licht, Marcela Alberto Amaya, Ciro Langevin, Andre Ecole Polytech Montreal Dept Math & Genie Ind Quebec City PQ Canada CIRRELT Montreal PQ Canada Univ Los Andes Dept Ingn Ind Bogota Colombia

The rural postman problem with Time Windows for the undirected case is introduced. The problem occurs in the monitoring of roads for black-ice detection. Different formulations are proposed and tested on sets of instances adapted from the literature. A cutting plane algorithm based on valid inequalities for the Traveling Salesman problem (TSP) with Time Windows and the Precedence Constrained TSP is presented as solution method and tested on a set of real-life networks. Computational results show that this approach is able to solve to optimality instances with up to 104 required edges. At the end of the article the formulations for the undirected case are extended to the directed case. (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 169-180 2014

关键词： rural postman problem time windows cutting plane algorithms monitoring of roads

来源：评论

学校读者我要写书评

暂无评论

Solving the large-scale min-max K-rural postman problem for snow plowing

引用

NETWORKS 2017年第3期70卷 195-215页

作者： Quirion-Blais, Olivier Langevin, Andre Lehuede, Fabien Peton, Olivier Trepanier, Martin Interuniv Res Ctr Enterprise Networks Logist & Tr Montreal PQ Canada Polytech Montreal Dept Math & Ind Engn Quebec City PQ Canada IMT Atlantique LS2N UMR CNRS 6004 Nantes France

This article studies the snow plow routing problem, which is a modified version of the min-max problem with k-vehicles for arc routing on a mixed graph with hierarchy. Each arc or edge is given a priority and instead of minimizing the overall finishing time, we minimize the latest finishing time for each priority class. We consider turn restrictions, route balancing, and variable vehicle speeds in a real large-scale network. To solve the problem, we present a graph transformation from a directed rural postman problem with turn penalties to an asymmetric traveling salesman problem. We then make the following modifications to the metaheuristics to better handle the constraints: development of new neighborhood operators, several applications of the same destruction operators before repair of the solution, and a dynamic arc-grouping procedure when links are removed or inserted. We tested our methodology on three real networks with 1,626 to 2,146 street segments and 613 to 723 intersections. The results show that our approach can improve the solution, and the grouping procedure is helpful. The results also show that some operators perform better than others;the network topology seems to explain these variations. Finally, we validated our methodology by comparing to some routes planned in the past and to some routes obtained from a commercial solver. (c) 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 195-215 2017

关键词： winter maintenance adaptive large neighborhood search rural postman problem large-scale real-life applications arc grouping network topology

来源：评论

学校读者我要写书评

暂无评论

A two-stage solution approach for the Directed rural postman problem with Turn Penalties

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第2期272卷 754-765页

作者： Cerrone, Carmine Dussault, Benjamin Wang, Xingyin Golden, Bruce Wasil, Edward Univ Molise Dept Biosci & Terr Campobasso Italy End To End Analyt LLC Palo Alto CA USA Singapore Univ Technol & Design Engn Syst & Design Singapore Singapore Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA Amer Univ Kogod Sch Business Washington DC 20016 USA

In this paper, we consider the Directed rural postman problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time. (C) 2018 Published by Elsevier B.V.

关键词： Routing Heuristics Greedy algorithm rural postman problem Turn penalties

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：