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

Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs

TRANSPORTATION SCIENCE 2019年第5期53卷 1409-1426页

作者： He, Qie Irnich, Stefan Song, Yongjia Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ D-55128 Mainz Germany Clemson Univ Dept Ind Engn Clemson SC 29634 USA

Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a network of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation and customers' inconvenience costs. In this paper, we introduce the vehicle routing problem with time windows and convex node costs (VRPTW-CNC), in which we model each customer's inconvenience cost as a convex function of the service start time at that customer. The VRPTW-CNC combines and extends both the standard vehicle muting problem with time windows and some previous results on the optimal service scheduling problem over a fixed route. We propose a branch-and-cut-and-price algorithm to solve the VRPTW-CNC with general convex inconvenience cost functions. To solve the pricing problem, our labeling algorithm only generates labels that possibly lead to optimal schedule times over a route, which significantly improves the effectiveness of pricing. Extensive computational results demonstrate the effectiveness of our approach.

关键词： vehicle routing problem branch-and-cut-and-price labeling algorithm convex node costs integrated routing and scheduling

来源：评论

学校读者我要写书评

暂无评论

A fast connected components labeling algorithm for binary images

引用

Journal of Harbin Institute of Technology(New Series) 2012年第3期19卷 81-87页

作者：付宜利韩现伟王树国 State Key Laboratory of Robotics and System Harbin Institute of Technology

A fast label-equivalence-based connected components labeling algorithm is proposed in this *** is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labeling *** is a fast pixel scan method,and the other is an array-based Union-Find data *** scan procedure assigns each foreground pixel a provisional label according to the location of the *** is to say,it labels the foreground pixels following background pixels and foreground pixels in different ways,which greatly reduces the number of neighbor pixel *** array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression,and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based *** experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components.

关键词： binary image connected components labeling algorithm Union-Find label-equivalence

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Connected components labeling based on union-find operations applied to connected branches

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2017年第5期32卷 3739-3748页

作者： Niu Lianqiang Chen Xin Peng Min Zhang Gang Shenyang Univ Technol Software Sch Shenyang Liaoning Peoples R China Shenyang Univ Technol Sch Sci Shenyang Liaoning Peoples R China

This paper presents an efficient run-based algorithm for labeling connected components in a binary image. By means of two tables called index table and equivalent information table respectively, the algorithm assign labels only to run sets which are composed of a series of runs connected to each other in adjacent scan rows, then the same index in equivalent information table can be assigned to all runs of a set in index table at one time. Further, the algorithm organizes all equivalence information in equivalent information table in a tree structure, and employee the union-find technique to merge connected components rapidly. The algorithm is very simple, and fewer operations are needed to check and to label runs of a connected branch. Furthermore, it is not necessary to calculate the minimum label while combining two runs, and is able to construct a union-find tree with smaller height. Thus the algorithm is able to provide a high speed to label connected components for general images.

关键词： Connected components union-find labeling algorithm label equivalent run length encoding

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A labeling algorithm for the sensitivity ranges of the assignment problem

引用

APPLIED MATHEMATICAL MODELLING 2011年第10期35卷 4852-4864页

作者： Lin, Chi-Jen Ta Hwa Inst Technol Dept Ind Engn & Management Hsinchu Taiwan

In view of the simplex-type algorithm, the assignment problem is inherently highly degenerate. It may be the optimal basis has changed, but the optimal assignment is unchanged when parameter variation occurs. Degeneracy then makes sensitivity analysis difficult, as well as makes the classical Type I range, which identifies the range the optimal basis unchanged, impractical. In this paper, a labeling algorithm is proposed to identify two other sensitivity ranges - Type II range and Type III range. The algorithm uses the reduced cost matrix, provided in the final results of most solution algorithms for AP, to determine the Type II range which reflects the stability of the current optimal assignment. Thus, the algorithm generates a streamlined situation from searching the optimal solution until performing the sensitivity analysis of the assignment problem. The Type III range, reflecting the flexibility of optimal decision making, can be obtained immediately after the Type II range is determined. Numerical examples are presented to demonstrate the algorithm. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Assignment problem Sensitivity analysis Degeneracy labeling algorithm

来源：评论

学校读者我要写书评

暂无评论

3-D street label visualization with an enhanced force-directed street labeling (FDSL) method

引用

SPATIAL INFORMATION RESEARCH 2016年第1期24卷 1-11页

作者： Kang, Yi Seul Park, Soo Hong Joo, Yong Jin Inha Univ Dept GeoInformat Engn Incheon South Korea Inha Tech Coll Aerial GeoInformat Incheon South Korea

To improve the parcel-based address system which has been used for the past 100 years, the street name address system has been fully enforced since 2014. The street labels are defined as an important factor for the recognition of locations and direction, but only labels of the buildings are shown in the current 3D spatial information services. To represent 3D spatial information without cluttering, solutions to minimize overlaps between labels and street labels hiding with building objects are required. Therefore, this study aims at improving the conventional 2.5D street labeling method, Force-directed Street labeling, designing a labeling algorithm applicable for 3-D space information services, and presenting an efficient visualization methods on a specific part of the Hannaru-ro in Incheon of 3-D spatial information services. The coefficient relationship equation is derived for viewing angles at which street labels are overlapped in a 3-D spatial information service, and this coefficient relationship equation is used in the designed algorithm to minimize overlaps. After the labels is placed, the selected visualization methods were applied to an actual 3-D spatial information service, which confirmed the visibility of street labels even among 3-D objects. As a result, users can recognize all street labels on the screen clearly with no confusion, and this will be helpful for the policy to stimulate the use of the street name address system.

关键词： Street name Label 3-D spatial information service FDSL labeling algorithm Visualization of label

来源：评论

学校读者我要写书评

暂无评论

Efficient scan mask techniques for connected components labeling algorithm

引用

EURASIP JOURNAL ON IMAGE AND VIDEO PROCESSING 2011年第1期2011卷 1-20页

作者： Sutheebanjard, Phaisarn Premchaiswadi, Wichian Siam Univ Grad Sch Informat Technol Bangkok 10160 Thailand

Block-based connected components labeling is by far the fastest algorithm to label the connected components in 2D binary images, especially when the image size is quite large. This algorithm produces a decision tree that contains 211 leaf nodes with 14 levels for the depth of a tree and an average depth of 1.5923. This article attempts to provide a faster method for connected components labeling. We propose two new scan masks for connected components labeling, namely, the pixel-based scan mask and the block-based scan mask. In the final stage, the block-based scan mask is transformed to a near-optimal decision tree. We conducted comparative experiments using different sources of images for examining the performance of the proposed method against the existing methods. We also performed an average tree depth analysis and tree balance analysis to consolidate the performance improvement over the existing methods. Most significantly, the proposed method produces a decision tree containing 86 leaf nodes with 12 levels for the depth of a tree and an average depth of 1.4593, resulting in faster execution time, especially when the foreground density is equal to or greater than the background density of the images.

关键词： connected components image processing labeling algorithm linear time algorithm pattern recognition

来源：评论

学校读者我要写书评

暂无评论

A Branch-Price-and-Cut algorithm for the Inventory-Routing Problem

引用

TRANSPORTATION SCIENCE 2016年第3期50卷 1060-1076页

作者： Desaulniers, Guy Rakke, Jorgen G. Coelho, Leandro C. Ecole Polytech Dept Math & Ind Engn Montreal PQ H3C 2A7 Canada Gerad Montreal PQ H3C 2A7 Canada Norwegian Univ Sci & Technol Dept Marine Technol N-7491 Trondheim Norway Univ Laval Fac Sci Adm Quebec City PQ G1V 0A6 Canada CIRRELT Quebec City PQ G1V 0A6 Canada

The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to service over a multiperiod horizon, the IRP consists of determining when to visit each customer, which quantity to deliver in each visit, and how to combine the visits in each period into feasible routes such that the total routing and inventory costs are minimized. In this paper, we propose an innovative mathematical formulation for the IRP and develop a state-of-the-art branch-price-and-cut algorithm for solving it. This algorithm incorporates known and new families of valid inequalities, including an adaptation of the well-known capacity inequalities, as well as an ad hoc labeling algorithm for solving the column generation subproblems. Through extensive computational experiments on a widely used set of 640 benchmark instances involving between two and five vehicles, we show that our branch-price-and-cut algorithm clearly outperforms a state-of-the-art branch-and-cut algorithm on the instances with four and five vehicles. In this instance set, 238 were still open before this work and we proved optimality for 54 of them.

关键词： inventory routing branch price and cut capacity inequalities labeling algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Branch-and-price algorithm for the location-routing problem with time windows

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2016年 86卷 1-19页

作者： Ponboon, Sattrawut Qureshi, Ali Gul Taniguchi, Eiichi Kyoto Univ Dept Urban Management Nishikyo Ku Kyoto 6158540 Japan

This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Location-routing problem Time windows Branch-and-price Column generation labeling algorithm Exact solution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：