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

Speeding up Martins' algorithm for multiple objective shortest path problems

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2013年第4期11卷 323-348页

作者： Demeyer, Sofie Goedgebeur, Jan Audenaert, Pieter Pickavet, Mario Demeester, Piet Univ Ghent Dept Informat Technol INTEC IBBT B-9050 Ghent Belgium

The latest transportation systems require the best routes in a large network with respect to multiple objectives simultaneously to be calculated in a very short time. The label setting algorithm of Martins efficiently finds this set of Pareto optimal paths, but sometimes tends to be slow, especially for large networks such as transportation networks. In this article we investigate a number of speedup measures, resulting in new algorithms. It is shown that the calculation time to find the Pareto optimal set can be reduced considerably. Moreover, it is mathematically proven that these algorithms still produce the Pareto optimal set of paths.

关键词： Multiobjective shortest path problem labeling algorithm Stop condition Bidirectional routing Pareto optimal set

来源：评论

学校读者我要写书评

暂无评论

Formulation and algorithms for route planning problem of plug-in hybrid electric vehicles

引用

OPERATIONAL RESEARCH 2018年第2期18卷 497-519页

作者： Murakami, Keisuke Kansai Univ 3-3-35 Yamate Suita Osaka 5648680 Japan

Electric vehicles have recently received increasing attention because of their positive environmental and economic impacts;however, such vehicles are still not gaining widespread popularity for practical use given the inconvenience of limited battery capacity and long recharge times. To compensate for these drawbacks, plug-in hybrid electric vehicles (PHEVs) have been proposed, which can be recharged using standard household plug-in sockets unlike normal hybrid vehicles. Thus, PHEVs can run for long distances using widely available electrical power. Scheduling routes for the efficient use of electrical power is essential for PHEVs to succeed. Therefore, in this paper, we consider the PHEV routing and scheduling problem. We first formulate this problem as a mixed-integer programming (MIP) problem. Next, we propose three algorithms using a labeling method for large-scale problems;an exact algorithm and two heuristic algorithms. Our computational experiments show that the routes obtained using our algorithms are cost-efficient;further, our heuristic algorithms are much faster than the MIP formulation.

关键词： Plug-in hybrid electric vehicle Routing and scheduling problem Mixed integer programming problem labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff

引用

OR SPECTRUM 2024年第4期46卷 1063-1097页

作者： Faldum, Stefan Machate, Sarah Gschwind, Timo Irnich, Stefan Johannes Gutenberg Univ Mainz Chair Logist Management Gutenberg Sch Management & Econ Jakob Welder Weg 9 D-55128 Mainz Germany RPTU Kaiserlautern Landau Chair Logist Sch Business & Econ Gottlieb Daimler Str 42 D-67663 Kaiserslautern Germany

For many variants of vehicle routing and scheduling problems solved by a branch-price-and-cut (BPC) algorithm, the pricing subproblem is an elementary shortest-path problem with resource constraints (SPPRC) typically solved by a dynamic-programming labeling algorithm. Solving the SPPRC subproblems consumes most of the total BPC computation time. Critical to the performance of the labeling algorithms and thus the BPC algorithm as a whole is the use of effective dominance rules. Classical dominance rules rely on a pairwise comparison of labels and have been used in many labeling algorithms. In contrast, partial dominance describes situations where several labels together are needed to dominate another label, which can then be safely discarded. In this work, we consider SPPRCs, where a linear tradeoff describes the relationship between two resources. We derive a unified partial dominance rule to be used in ad hoc labeling algorithms for solving such SPPRCs as well as insights into its practical implementation. We introduce partial dominance for two important variants of the vehicle routing problem, namely the electric vehicle routing problem with time windows with a partial recharge policy and the split-delivery vehicle routing problem with time windows (SDVRPTW). Computational experiments show the effectiveness of the approach, in particular for the SDVRPTW, leading to an average reduction of 20% of the total BPC computation time, with savings of 30% for the more difficult instances requiring more than 600 s of computation time.

关键词： Branch-price-and-cut Partial dominance Column generation labeling algorithm Vehicle routing and scheduling

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for two-echelon electric vehicle routing problem

引用

COMPLEX & INTELLIGENT SYSTEMS 2023年第3期9卷 2475-2490页

作者： Wu, Zhiguo Zhang, Juliang Beijing Jiaotong Univ Sch Econ & Management Beijing Peoples R China

Motivated by express and e-commerce companies' distribution practices, we study a two-echelon electric vehicle routing problem. In this problem, fuel-powered vehicles are used to transport goods from a depot to intermediate facilities (satellites) in the first echelon, whereas electric vehicles, which have limited driving ranges and need to be recharged at recharging stations, are used to transfer goods from the satellites to customers in the second echelon. We model the problem as an arc flow model and decompose the model into a master problem and pricing subproblem. We propose a branch-and-price algorithm to solve it. We use column generation to solve the restricted master problem to provide lower bounds. By enumerating all the subsets of the satellites, we generate feasible columns by solving the elementary shortest path problem with resource constraints in the first echelon. Then, we design a bidirectional labeling algorithm to generate feasible routes in the second echelon. Comparing the performance of our proposed algorithm with that of CPLEX in solving a set of small-sized instances, we demonstrate the former's effectiveness. We further assess our algorithm in solving two sets of larger scale instances. We also examine the impacts of some model parameters on the solution.

关键词： Two-echelon Electric vehicles Branch-and-price algorithm Column generation labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A Heuristic algorithm for Substrates Testing in MCM

A Heuristic Algorithm for Substrates Testing in MCM

引用

IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)

作者： Murakami, Keisuke Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781457707391

Multi-chip module (MCM) substrate is designed to pack two or more semiconductor chips. On a MCM substrate, there might exist a few types of faults in the wiring. Thus, it is essential to establish an efficient method for testing in MCM to detect faults. This paper presents a heuristic algorithm for substrates testing in MCM. Our objective is to minimize the completion time of the testing. The testing is performed by two equipments, called probe. Several previous works propose a method for the testing. Although the method finds at least one feasible solution fast, there is no guarantee that the solution is always good. Therefore, we formulate a testing problem as a shortest path problem with covering constraints (SPCC) and then, we propose a heuristic algorithm for the SPCC. In computation experiments, we show the SPCC approach are superior to the existing method.

关键词： labeling algorithm MCM substrates probe testing shortest path problem with covering constraints

来源：评论

学校读者我要写书评

暂无评论

Problems of projection

引用

LINGUA 2013年 130卷 33-49页

作者： Chomsky, Noam MIT Dept Linguist & Philosophy Cambridge MA 02139 USA

With the crystallization of the "generative enterprise" half a century ago, two concepts became salient: the initial state and final states of the language faculty, respectively, UG (the genetic component) and I-languages. Since then inquiry has gained far greater scope and depth. It has also led to sharpening of fundamental principles of language. At first, descriptive adequacy appeared to require rich and complex assumptions about UG. A primary goal has always been to overcome this deficiency. Core properties of concem have included compositionality, order, projection (labeling), and displacement. Early work assigned the first three to phrase structure rules and the last to the transformational component. Simplification of computational procedures suggests that compositionality and displacement (along with the "copy theory") fall together while order may be a reflex of sensorimotor externalization, conclusions that have far-reaching consequences. As for labeling, minimal computation restricts options to the few that have considerable empirical support. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Syntax Minimal computation Merge labeling algorithm Minimal search

来源：评论

学校读者我要写书评

暂无评论

On the generalized elementary shortest path problem: A heuristic approach

引用

Electronic Notes in Discrete Mathematics 2013年 41卷 503-510页

作者： Guerrero, W.J. Velasco, N. Prodhon, C. Amaya, C.A. Pylo School of Engineering Universidad de los Andes Bogotá Cra 1 Este No 19A - 40 Colombia ICD-LOSI (UMR-STMR CNRS 6279) Université de Technologie de Troyes CS 42060 10004 Troyes Cedex 12 rue Marie Curie France Invited Professor ICD-LOSI (CNRS 6279) Université de Technologie de Troyes CS 42060 10004 Troyes Cedex 12 rue Marie Curie France

We introduce the generalized elementary shortest path problem (GESPP) where in addition to the features of the shortest path problem, nodes belong to predefined non-disjoint clusters. Each cluster is associated to a profit to the cost function, obtained if at least one element in the cluster appears in the path. Several applications can be considered as school bus routing, pricing problems, or telecommunication network design. Thus, depending on the case, clusters could be interpreted as groups of nodes with linking features as, for example, being easily reachable from each other, or some kind of coverage guarantee. We compare the GESPP to similar problems in the literature and we propose a two-phase heuristic algorithm for graphs including negative cycles. Tests on random instances with up to 100 nodes show an average gap of 0.3% to the best known solutions computed in 2.8s in average. © 2013 Elsevier B.V.

关键词： Elementary shortest path problem labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for skew correction and baseline detection based on the randomized Hough Transform

引用

JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES 2017年第1期29卷 29-38页

作者： Boukharouba, Abdelhak Univ 8 Mai 1945 Guelma Dept Elect & Telecommun Fac Sci & Technol BP 401 Guelma 24000 Algeria

The proposed technique is based on the detection of the lower baselines of the text lines of Arabic documents. As the lower baseline pixels belong to the lower edge of the word images, we first locate vertically the black-white transitions at the black pixels where the resulting image would emphasize the baselines of the text. Once the skew angle is determined using a randomized Hough transform, the baselines are extracted using gamma-intercept histogram. This algorithm can also contribute significantly for text line extraction from skewed document images for many languages. (C) 2016 King Saud University. Production and hosting by Elsevier B.V.

关键词： Document lower edge extraction labeling algorithm Randomized Hough transform Skew correction Baseline detection

来源：评论

学校读者我要写书评

暂无评论

Content-based retrieval system using Artificial Hippocampus algorithm

Content-based retrieval system using Artificial Hippocampus ...

引用

11th World Multi-Conference on Systemics, Cybernetics and Informatics/13th International Conference on Information Systems Analysis and Synthesis

作者： Chu, Jung-Ho Kim, Young Ho Kang, Dae-Seong Dong A Univ Dept Elect Engn Pusan 604714 South Korea

ISBN: (纸本)9781934272169

As information-oriented society at the beginning 21 centuries, many kinds of multimedia data are used variously and requirements for effective use by user are increasing. In order to transfer information fast and precisely what user wants, retrieval method is required. Recently there have been many efforts to support searching and browsing based on the visual content of image and multimedia data. In this paper, we propose a user friendly object-based image retrieval system using labeling algorithm and Artificial Hippocampus algorithm (AHA). Most existing ways of queries in content-based image retrieval rely on query by example or query by sketch. But these methods of queries are not adequate to needs of people's various queries because they are not easy for people to use and restrict. We propose a method of automatic color object extraction using CSB tree map (Color and Spatial based Binary tree map). Extracted objects were transformed to bit stream representing information such as color, size and location by region labeling representing information such as color, size and location by region labeling algorithm and they are learned by the hippocampus neural network using the interplay between cortex and hippocampus. Various phenomena generated in the brain are hidden in the veil of mystery. In the engineering put, neural network grounded on learning and memory of the brain is applied to many parts. In neural network., learning is considered transferring and processing of the information by each neuron connected synapse. When a stimulus is given, the material of the molecule unit which contains information in the pre-synapse is activated and progressed to the postsynapse. While it is processing, a molecule or the dynamics of stromata is continuous and is generated parallel. The existing neural network generated by learning method of Hebb is different from a model of a real brain. Network present database of all features of images such as color histogram of the image,

关键词： Artificial Hippocampus algorithm (AHA) content-based image retrieval CSB tree map (Color and Spatial based Binary tree map) Single Colorizing labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

A Continuous Time Model of Multi-vehicle Routing Problems: A Column Generation Approach

A Continuous Time Model of Multi-vehicle Routing Problems: A...

引用

IEEE International Conference on Systems, Man, and Cybernetics (SMC)

作者： Matsushita, Susumu Nishi, Tatsushi Morikawa, Masashi Hisano, Takeshi Osaka Univ Grad Sch Engn Sci 1-3 Machikaneyama Cho Toyonaka Osaka 560 Japan Daifuku Co Ltd Shiga Japan

ISBN: (纸本)9781479906529

In this paper, we propose a column generation heuristics to a continuous time model of conflict-free pickup and delivery vehicle routing problems. The transportation system is divided into several regions with regular intervals. A network model of conflict-free multi-vehicle routing problem with acceleration and deceleration motions is developed. A column generation heuristics is used to find a near-optimal solution. The pricing problem for each vehicle routing problem is formulated as a resource constrained shortest path problem, which is effectively solved by a labeling algorithm. Computational results demonstrate the effectiveness of the proposed method.

关键词： automated guided vehicle acceleration motion column generation routing labeling algorithm heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：