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

label-setting algorithm for Multi-Destination K Simple Shortest Paths Problem and Application

algorithmS 2024年第8期17卷 325页

作者： Udhayasekar, Sethu Vinayagam Srinivasan, Karthik K. Kumar, Pramesh Chilukuri, Bhargava Rama Indian Inst Technol Madras Dept Civil Engn Chennai 600036 India Indian Inst Technol Delhi Dept Civil Engn New Delhi 110016 India

The k shortest paths problem finds applications in multiple fields. Of particular interest in the transportation field is the variant of finding k simple shortest paths (KSSP), which has a higher complexity. This research presents a novel label-setting algorithm for the multi-destination KSSP problem in directed networks that obviates repeated applications of the algorithm to each destination (necessary in existing deviation-based algorithms), resulting in a significant computational speedup. It is shown that the proposed algorithm is exact and flexible enough to handle several variants of the problem by appropriately modifying the termination condition. Theoretically, it is also shown to be faster than state-of-the-art algorithms in sparse and dense networks whenever the number of labels created is sub-polynomial in network size. A heuristic method and optimized data structures are proposed to improve the algorithm's scalability and worst-case performance. The computational results show that the proposed heuristic provides two to three orders of magnitude computational time speedups (29-1416 times across different networks) with negligible loss in solution quality (maximum average deviation of 0.167% from the optimal solution). Finally, a practical application of the proposed method is illustrated to determine the gravity of an edge (relative structural importance) in a network.

关键词： k simple shortest paths label-setting algorithm loopless paths network optimization edge importance edge ranking

来源：评论

学校读者我要写书评

暂无评论

Exact Approach for Integrated Delivery Optimization of E-Commerce and Online-to-Offline Parcels

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第3期40卷 2250026-2250026页

作者： Pu, Song Xia, Chang Chengdu Technol Univ Sch Econ & Management Chengdu 611730 Peoples R China

This paper studies a novel form of last-mile delivery that combines delivery optimization of E-commerce and Online-to-Offline (O2O) parcels. While O2O parcels must first be picked up from O2O shops before being delivered to the appropriate customers, E-commerce parcels are delivered to customers from a predetermined number of depots. The goal is to use the same fleet of vehicles to provide integrated delivery services for various merchant types. We propose a branch-and-price algorithm based on the set partitioning formulation, where the pricing problem is solved by a label-setting algorithm. Several acceleration techniques including elementary path relaxation, ng-path relaxation and decremental space search are designed to speed up the price problem. Both the conventional dataset used in the literature and a real-world database with up to 75 clients are utilized to test the performance of the suggested method, demonstrating its efficacy.

关键词： Vehicle routing pickup and delivery problem branch-and-price label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Exact algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries

引用

INFORMS JOURNAL ON COMPUTING 2023年第1期35卷 31-49页

作者： Li, Jiliu Luo, Zhixing Baldacci, Roberto Qin, Hu Xu, Zhou Northwestern Polytech Univ Sch Management Xian 710072 Peoples R China Nanjing Univ Sch Management & Engn Nanjing 210008 Peoples R China Hamad Bin Khalifa Univ Coll Sci & Engn Engn Management & Decis Sci Doha Qatar Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China Hong Kong Polytech Univ Fac Business Hong Kong Peoples R China

We present a new exact algorithm to solve a challenging vehicle routing problem with split pickups and deliveries, named as the single-commodity split-pickup and split -delivery vehicle routing problem (SPDVRP). In the SPDVRP, any amount of a product col-lected from a pickup customer can be supplied to any delivery customer, and the demand of each customer can be collected or delivered multiple times by the same or different vehicles. The vehicle fleet is homogeneous with limited capacity and maximum route duration. This problem arises regularly in inventory and routing rebalancing applications, such as in bike -sharing systems, where bikes must be rebalanced over time such that the appropriate num-ber of bikes and open docks are available to users. The solution of the SPDVRP requires determining the number of visits to each customer, the relevant portions of the demands to be collected from or delivered to the customers, and the routing of the vehicles. These three decisions are intertwined, contributing to the hardness of the problem. Our new exact algo-rithm for the SPDVRP is a branch-price-and-cut algorithm based on a pattern-based mathe-matical formulation. The SPDVRP relies on a novel label-setting algorithm used to solve the pricing problem associated with the pattern-based formulation, where the label components embed reduced cost functions, unlike those classical components that embed delivered or collected quantities, thus significantly reducing the dimension of the corresponding state space. Extensive computational results on different classes of benchmark instances illustrate that the newly proposed exact algorithm solves several open SPDVRP instances and signifi-cantly improves the running times of state-of-the-art algorithms.

关键词： vehicle routing single commodity split pickups split deliveries branch-price-and-cut label-setting algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An offline map matching algorithm based on shortest paths

引用

INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE 2021年第11期35卷 2238-2261页

作者： Zhang, Dongqing Guo, Zhaoxia Guo, Feng Dong, Yucheng Sichuan Univ Sch Business Chengdu Peoples R China

Offline map matching identifies corresponding roads to a GPS trajectory represented by a series of recorded geographic coordinates (GPS points) to the road network. This paper defines matching error as cost on the corresponding road-link to matched GPS points and formulates the offline map matching problem as a shortest path problem with resource constraints. By regarding matched points on one link as a type of resource consumed, the resource constraint indicates that the number of matched GPS points equals the total number of points in the given trajectory. We propose an offline map matching algorithm based on shortest paths by calculating the matching error on each link and extending the classic label-setting shortest path algorithm to find the path with the minimum total matching error for all GPS points. We use real-world taxi trajectories to compare our algorithm with three state-of-the-art map matching algorithms. Our algorithm outperforms all benchmark algorithms in terms of both matching accuracy and computational efficiency. Our algorithm achieves greater matched length (5.36 to 12.27% larger) and lower mis-matched length (3.72 to 75.30% smaller) at a very high matching speed (60.59 points per second on average over thirteen sampling intervals).

关键词： GPS trajectory resource constraints label-setting algorithm time-dependence

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the multi-period inspector scheduling problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 145卷 106515-106515页

作者： Shen, Huaxiao Shu, Shengnan Qin, Hu Wu, Qinghua Sun Yat Sen Univ Guangzhou 510275 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China

In this paper, we study the multi-period inspector scheduling problem (MPISP). This problem aims to determine a set of routes for a team of inspectors performing inspection jobs in different locations across multiple days, with the objective of maximizing the total workloads that the inspectors undertake. Since an inspector can only perform inspections or travel during working periods and rest at other times, a route for an inspector is divided into several segments. This characteristic, on the one hand, differentiates the MPISP from many routing problems in the literature;on the other hand, however, makes the routing decisions more complicated and challenging. To solve the MPISP, we first formulate it into a set-packing model and then propose an exact branchand-price algorithm. In particular, we design a tailored label-setting algorithm for the pricing subproblem, which is a variant of the elementary shortest path problem with resource constraints. Moreover, we implement some acceleration techniques, such as bidirectional search, label pruning, decremental search space relaxation, and heuristic column generator. Extensive computational experiments were conducted on a set of benchmark instances, and the results have demonstrated the effectiveness of the proposed algorithm.

关键词： Routing Inspector scheduling problem Multi-period Exact algorithm Branch-and-price label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

Determining time-dependent minimum cost paths under several objectives

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 105卷 102-117页

作者： Heni, Hamza Coelho, Leandro C. Renaud, Jacques Interuniv Res Ctr Enterprise Networks Logist & Tr Montreal PQ Canada Laval Univ Fac Business Adm Quebec City PQ Canada Canada Res Chair Integrated Logist Quebec City PQ Canada Ctr Innovat Logist & Chaine Approvisionnement Dur Quebec City PQ Canada

As the largest contributor to greenhouse gas (GHG) emissions in the transportation sector, road freight transportation is the focus of numerous strategies to tackle increased pollution. One way to reduce emissions is to consider congestion and being able to route traffic around it. In this paper we study time-dependent minimum cost paths under several objectives (TDMCP-SO), in which the objective function comprises GHG emissions, driver and congestion costs. Travel costs are impacted by traffic due to changing congestion levels depending on the time of the day, vehicle types and carried load. We also develop time-dependent lower and upper bounds, which are both accurate and fast to compute. Computational experiments are performed on real-life instances that incorporate the variation of traffic throughout the day, by adapting Dijkstra's label-setting algorithm according to different cost computation methods. We show that explicitly considering first-in, first-out (FIFO) consistency using time-varying speeds allows the efficient computation of tight time-dependent bounds. Our computational results demonstrate that the TDMCP-SO is more difficult to solve to optimality but the proposed algorithm is shown to be robust and efficient in reducing the total cost even for large instances in an environment of varying speeds, outperforming those based on the link travel time model and on the smoothing method according to each optimization objective, flexible departure times, and different load patterns. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Time-dependent networks Congestion Emission Quickest path Bounds label-setting algorithm Link travel time Flow speed model

来源：评论

学校读者我要写书评

暂无评论

Robust constrained shortest path problems under budgeted uncertainty

引用

NETWORKS 2015年第2期66卷 98-111页

作者： Pessoa, Artur Alves Pugliese, Luigi Di Puglia Guerriero, Francesca Poss, Michael Univ Fed Fluminense Dept Prod Engn BR-24210240 Niteroi RJ Brazil Univ Calabria Dept Mech Energy & Management Engn I-87036 Arcavacata Di Rende Italy Univ Montpellier 2 CNRS UMR 5506 LIRMM 161 Rue Ada F-34392 Montpellier 5 France

We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is NP-hard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the problem with capacity constraints can be solved in pseudopolynomial time. However, we prove that the problem with time windows is NP-hard in the strong sense when NP is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudopolynomial when NP is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty. (c) 2015 Wiley Periodicals, Inc.

关键词： robust optimization budgeted uncertainty dynamic programming np-hard label-setting algorithm constrained shortest path time windows

来源：评论

学校读者我要写书评

暂无评论

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 57卷 83-94页

作者： Sedeno-Noda, Antonio Raith, Andrea Univ La Laguna Dept Matemat Estadist & Invest Operat San Cristobal De La Lagu 38271 Santa Cruz De T Spain Univ Auckland Dept Engn Sci Auckland New Zealand

We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra's algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Biobjective path problems Supported efficient paths label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems

引用

NETWORKS 2008年第4期52卷 256-270页

作者： Carlyle, W. Matthew Royset, Johannes O. Wood, R. Kevin USN Postgrad Sch Dept Operat Res Monterey CA USA

The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible solution, and then closes any optimality gap by enumerating near-shortest paths, measured with respect to the Lagrangianized length. "Near-shortest" implies epsilon-optimal, with a varying c that equals the current optimality gap. The algorithm exploits a variety of techniques: a new path-enumeration method;aggregated constraints;preprocessing to eliminate edges that cannot form part of an optimal solution;"reprocessing" that reapplies preprocessing steps as improved solutions are found;and, when needed, a "phase-I procedure" to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art label-setting algorithm on singly constrained randomly generated grid networks. On multiconstrained grid networks, road networks, and networks for aircraft routing the advantage varies but, overall, the new algorithm is competitive with the label-setting algorithm. 0 2008 Wiley Periodicals, Inc.* NETWORKS, Vol. 52(4), 256-270 2008

关键词： constrained shortest paths near-shortest paths Lagrangian relaxation path enumeration label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

On solving dynamic shortest path problems 20

On solving dynamic shortest path problems

引用

20th International Conference/Euro Mini Conference on Continuous Optimization and Knowledge-Based Technologies (EurOPT 2008)

作者： Nasrabadi, Ebrahim Hashemi, S. Mehdi Amirkabir Univ Technol Dept Comp Sci Tehran Iran

ISBN: (纸本)9789955282839

Given a dynamic network with n nodes and m arcs in which all attributes including travel times, travel costs and waiting costs may change dynamically over a time horizon T. The dynamic shortest path problem is to determine a path from a specified source node to every other node with minimal total cost, subject to the constraint that the total traverse time is at most T. This problem can be formulated in two ways depending on whether a discrete or continuous representation of time is used. In this paper, we present an O(nT(n+T)) time algorithm for solving the discrete-time version of dynamic shortest path problem.

关键词： dynamic networks dynamic shortest path label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：