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

A general label setting algorithm and tractability analysis for the multiobjective temporal shortest path problem

NETWORKS 2025年第1期85卷 76-90页

作者： Bazgan, Cristina Kager, Johannes Thielen, Clemens Vanderpooten, Daniel Univ Paris 09 PSL Res Univ CNRS LAMSADE Paris France Weihenstephan Triesdorf Univ Appl Sci TUM Campus Straubing Biotechnol & Sustainabil Straubing Germany Tech Univ Munich Sch Computat Informat & Technol Dept Math Garching Germany

Given a directed temporal graph, a start node s$$ s $$, and p$$ p $$ objectives, the task in the single-source multiobjective temporal shortest path problem (SSMTSPP) consists of computing the set of nondominated images of temporal s$$ s $$-v$$ v $$-paths for each node v not equal s$$ v\ne s $$ as well as one corresponding efficient path for each of these images. This problem generalizes both the multiobjective shortest path problem in static graphs and the single-objective temporal shortest path problem. In this article, we provide a general label setting algorithm for the SSMTSPP that can handle a large variety of different objectives. The only condition imposed on the objectives is a monotonicity property that generalizes the nonnegativity of the arc costs required for the well-known label setting algorithm for solving the static single-source shortest path problem in both the single objective and the multiobjective case. Our analysis of the presented algorithm shows that its worst-case running time is polynomial in the sum of the input size of the problem instance and the number of nondominated images, which implies that it runs in polynomial time as long as the number of nondominated images is polynomial in the instance size (i.e., for all tractable versions of the problem). To complement this result, we provide a complete classification into tractable and intractable problems for all SSMTSPPs involving a large variety of objectives. In particular, using our general analysis, this provides a large range of specific SSMTSPPs for which our general label setting algorithm runs in polynomial time.

关键词： algorithm analysis label setting algorithm multiobjective optimization shortest paths temporal graphs tractability

来源：评论

学校读者我要写书评

暂无评论

Routing and charging scheduling for the electric carsharing system with mobile charging vehicles

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2025年 131卷

作者： Zhang, Li Chen, Tingting Yao, Baozhen Yu, Bin Wang, Yunpeng Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China Minist Educ Key Lab Intelligent Transportat Technol & Syst Beijing 100191 Peoples R China Hong Kong Polytech Univ Dept Aeronaut & Aviat Engn Hung Hom Hong Kong 999077 Peoples R China Dalian Univ Technol Sch Mech Engn Dalian 116024 Peoples R China

Electric carsharing systems are expected to be an optional alternative to private vehicles for decreasing the urban traffic congestion and emissions. However, the temporal and spatial imbalance of the charging demand of shared electric vehicles adds to the managerial complexity of electric carsharing systems. This paper integrates mobile charging vehicles into the electric carsharing system to address this imbalance. Mobile charging vehicles can dwell at stations to provide elastic charging capacity, and thereby decrease both the waiting time of shared electric vehicles at busy stations and the investments in fixed charging piles at suburban stations. In this paper, a mixed integer linear programming formulation is proposed based on a time-space network, in which the routes of shared electric vehicles, charging schedules of shared electric vehicles, and routes of mobile charging vehicles are optimized simultaneously. Then, an algorithm based on Lagrangian relaxation is proposed. Specifically, the proposed formulation is decomposed into three independent subproblems. We propose three exact algorithms for these subproblems, and a tailored multistep repair algorithm is designed to generate feasible solutions. A case study in Hefei, China demonstrates the performance of the proposed algorithm and the effects of the number of SEVs, the number of MCVs, the number of fixed charging piles, trip component, battery capacity, and revenue on the operation of the electric carsharing system.

关键词： Shared electric vehicles Mobile charging vehicles Time-space network Lagrangian relaxation label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving open vehicle problem with time window by hybrid column generation algorithm

引用

Journal of Systems Engineering and Electronics 2022年第4期33卷 997-1009页

作者： YU Naikang QIAN Bin HU Rong CHEN Yuwang WANG Ling School of Mechanical and Electrical Engineering Kunming University of Science and TechnologyKunming 650500China School of Information Engineering and Automation Kunming University of Science and TechnologyKunming 650500China Yunnan Key Laboratory of Artificial Intelligence Kunming University of Science and TechnologyKunming 650500China Alliance Manchester Business School University of ManchesterManchester M139SSU.K. Department of Automation Tsinghua UniversityBeijing 100084China

This paper addresses the open vehicle routing problem with time window(OVRPTW), where each vehicle does not need to return to the depot after completing the delivery *** optimization objective is to minimize the total distance. This problem exists widely in real-life logistics distribution *** propose a hybrid column generation algorithm(HCGA) for the OVRPTW, embedding both exact algorithm and metaheuristic. In HCGA, a label setting algorithm and an intelligent algorithm are designed to select columns from small and large subproblems, respectively. Moreover, a branch strategy is devised to generate the final feasible solution for the OVRPTW. The computational results show that the proposed algorithm has faster speed and can obtain the approximate optimal solution of the problem with 100 customers in a reasonable time.

关键词： open vehicle routing problem with time window(OVRPTW) hybrid column generation algorithm(HCGA) mixed integer programming label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

An intermodal transport network planning algorithm using dynamic programming-A case study: from Busan to Rotterdam in intermodal freight routing

引用

APPLIED INTELLIGENCE 2012年第3期36卷 529-541页

作者： Cho, Jae Hyung Kim, Hyun Soo Choi, Hyung Rim Dong A Univ Dept Management Informat Syst Pusan 602760 South Korea Pusan Univ Foreign Studies Sch Int Business & Area Studies Pusan 608738 South Korea

This paper presents a dynamic programming algorithm to draw optimal intermodal freight routing with regard to international logistics of container cargo for export and import. This study looks into the characteristics of intermodal transport using multi-modes, and presents a Weighted Constrained Shortest Path Problem (WCSPP) model. This study draws Pareto optimal solutions that can simultaneously meet two objective functions by applying the label setting algorithm, a type of Dynamic Programming algorithms, after setting the feasible area. To improve the algorithm performance, pruning rules have also been presented. The algorithm is applied to real transport paths from Busan to Rotterdam, as well as to large-scale cases. This study quantitatively measures the savings in both transport cost and time by comparing single transport modes with intermodal transport paths. Last, this study applies a mathematical model and MADM model to the multiple Pareto optimal solutions to estimate the solutions.

关键词： Intermodal freight routing problem Dynamic programming Weighted constrained shortest path problem label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for time-dependent bicriteria shortest path problems

引用

DISCRETE OPTIMIZATION 2006年第3期3卷 238-254页

作者： Hamacher, Horst W. Ruzika, Stefan Tjandra, Stevanus A. Univ Kaiserslautern Fachbereich Math D-6750 Kaiserslautern Germany Univ Alberta Sch Business Edmonton AB Canada

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs. (c) 2006 Elsevier B.V. All rights reserved.

关键词： multiple criteria optimization label setting algorithm time-dependent shortest path problem bicriteria shortest path problem

来源：评论

学校读者我要写书评

暂无评论

A COMPUTATION METHOD ON TIME-DEPENDENT ACCESSIBILITY OF URBAN RAIL TRANSIT NETWORKS FOR THE LAST SERVICE

引用

TRANSPORT 2020年第1期35卷 26-36页

作者： Chen, Yao Mao, Baohua Bai, Yun Li, Zhujun Tang, Jimeng Beijing Jiaotong Univ Key Lab Transport Ind Big Data Applicat Technol C Beijing Peoples R China

Urban rail transit networks seldom provide 24-hour service. The last train is the latest chance for passengers. If passengers arrive too late to catch the last train, the path becomes inaccessible. The network accessibility thus varies depending on the departure time of passenger trips. This paper focuses on the computation method on the time-dependent accessibility of urban rail transit networks in order to facilitate the itinerary planning of passengers. A label setting algorithm is first designed to calculate the latest possible times for Origin-Destination (O-D) pairs, which is the latest departure times of passengers from the origins such that the destinations can be reach successfully. A searching approach is then developed to find the shortest accessible path at any possible departure times. The method is applied in a real-world metro network. The results show that the method is a powerful tool in solving the service accessibility problem. It has the ability to allow passengers to plan an optimal itinerary. Comparison analysis indicates that the proposed method can provide exact solutions in much shorter time, compared with a path enumeration method. Extensive tests on a set of random networks indicate that the method is efficient enough in practical applications. The execution time for an O-D pair on a personal computer with 2.8 GHZ CPU and 4GB of RAM is only 1.2 s for urban rail transit networks with 100 transfer stations.

关键词： urban rail transit network accessibility itinerary planning last train timetable label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

A comparison of solution strategies for biobjective shortest path problems

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第4期36卷 1299-1331页

作者： Raith, Andrea Ehrgott, Matthias Univ Auckland Dept Engn Sci Auckland 1 New Zealand Univ Nantes Lab Informat Nantes Atlantique F-44035 Nantes France

We consider the biobjective shortest path (BSP) problem as the natural extension of the single-objective shortest path problem. BSP problems arise in various applications where networks usually consist of large numbers of nodes and arcs. Since obtaining the set of efficient solutions to a BSP problem is more difficult (i.e. NP-hard and intractable) than solving the corresponding single-objective problem there is a need for fast solution techniques. Our aim is to compare different strategies for solving the BSP problem. We consider a standard label correcting and label setting method, a purely enumerative near shortest path approach, and the two phase method, investigating different approaches to solving problems arising in phases 1 and 2. In particular, we investigate the two phase method with ranking in phase 2. In order to compare the different approaches. we investigate their performance oil three different types of networks. We employ grid networks and random networks, as is generally done in the literature. Furthermore, road networks are utilized to compare performance on networks with a structure that is more likely to actually arise in applications. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Biobjective shortest path problem Two phase method label correcting algorithm label setting algorithm Near shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

Airport gate assignment problem with harbor constraints based on Branch-and-Price algorithm

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2023年第1期176卷

作者： Jiang, Yu Wang, Yasha Hu, Zhitao Xue, Qingwen Yu, Bin Nanjing Univ Aeronaut & Astronaut Coll Civil Aviat Nanjing 210016 Peoples R China Southeast Univ Sch Transportat Nanjing 211189 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Gen Aviat & Flight Nanjing 210016 Peoples R China Minist Educ Key Lab Intelligent Transportat Technol & Syst Beijing 100191 Peoples R China Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China

The airport gate assignment problem is the main problem in airport operation management. Most existing studies on the airport gate assignment problem focus more on the improvement of gate utilization efficiency and ignore apron operation safety. Aiming at addressing this problem, an airport gate assignment problem with harbor safety constraints is proposed in this paper. A two-phase mathematical optimization model is constructed to optimize the efficiency of gate utili-zation considering the safety constraints in harbors. To the best of our knowledge, this is the first study to explicitly focus on harbor apron security in the gate assignment problem. Then, the exact branch-and-price method is improved by incorporating a label-based pricing algorithm and two acceleration strategies. These strategies include an upper bound prediction strategy for handling the large number of subproblems and a lower parameter symmetry elimination strategy to overcome column generation degradation. The results show that the proposed gate assignment model and improved branch-and-price method optimize the efficiency of gate utilization under the condition of avoiding security conflicts in harbor aprons. The improved branch-and-price method has advantages in terms of both accuracy and efficiency compared with those of other solvers.

关键词： Airport gate assignment problem Harbor apron Branch-and-price Column generation label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

The constrained reliable shortest path problem for electric vehicles in the urban transportation network

引用

JOURNAL OF CLEANER PRODUCTION 2020年 261卷 121130-121130页

作者： Tu, Qiang Cheng, Lin Yuan, Tengfei Cheng, Yang Li, Manman Southeast Univ Sch Transportat Nanjing 211189 Peoples R China Minist Educ Key Lab Rd & Traff Engn Shanghai 201804 Peoples R China Tongji Univ Sch Transportat Engn 4800 Caoan Rd Shanghai 201804 Peoples R China Univ Wisconsin Dept Civil & Environm Engn Madison WI 53705 USA

Electric vehicles (EVs) have recently received increasing attention, because of the environment-friendly features. As one of the major concerns of electric vehicles, the path planning problem in urban transportation networks faces the difficulties of the travel time uncertainty and driving range limitation, due to the unexpected congestion, bad weather and battery capacity. This paper investigates the constrained reliable shortest path (CRSP) problem for electric vehicles in the urban transportation network. A mixed-integer programming model is developed for the CRSP problem, where the reliable travel time is treated as the objective and the energy consumption, instead of the distance, is taken as the driving range constraint. To simply the scale of the problem, some pre-processing and network reduction techniques are introduced. Then a label setting algorithm based on elaborate dominance conditions is proposed to solve this problem. Besides, the A* technique is integrated to improve the search performance of the algorithm. The proposed model and algorithms are tested in two real-world urban transportation networks and scalable grid networks. Numerical studies show that the path choice is impacted by the risk attitudes of travelers and the battery capacity of electric vehicles. It implies that the navigation system should customize the optimal path in more detail to satisfy travelers' heterogeneous requests. The proposed algorithm can obtain the exact solutions within satisfactory computational time, and it can be embedded into the intelligent navigation system to help the government promote the adoption of electric vehicles. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Electric vehicles Constrained reliable shortest path Travel time reliability Non-dominated solutions label setting algorithm

来源：评论

学校读者我要写书评

暂无评论

Construction of a correct combination of estimation algorithms adjusted using the cross validation technique

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2015年第12期55卷 2094-2099页

作者： Ignat'ev, O. A. Yandex Moscow 119021 Russia

A scheme for constructing a combination of estimation algorithms that is correct on a given training sample is proposed. The basic elements of the combination are algorithms obtained using the cross validation trainin... 详细信息

关键词： estimation algorithm label setting algorithm cross validation with respect to individual objects

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：