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

An exact decomposition method to save trips in cooperative pickup and delivery based on scheduled trips and profit distribution

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 87卷 245-257页

作者： Yu, Yang Lou, Qi Tang, Jiafu Wang, Junwei Yue, XiaoHang Northeastern Univ Inst Syst Engn Shenyang 110816 Liaoning Peoples R China Dongbei Univ Finance & Econ Coll Management Sci & Engn Dalian 116023 Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Pokfulam Rd Hong Kong Hong Kong Peoples R China Univ Wisconsin Lubar Sch Business Milwaukee WI 53201 USA

Compared to the non-cooperative mode, the cooperative mode is a powerful way to reduce operational cost in pickup and delivery service. In order to protect business sensitive information, sometimes participants are unwilling to open the customer's detailed information. Thus, we utilize the publishable trip scheduled results to compute the saved trips brought by cooperation. A mathematical model minimizing trips of cooperation is proposed. To obtain the exact solution, we define the cooperative trip set. We prove that only when cooperative trip set exists it is possible to save trips by cooperation. For a two-trip cooperative trip set, we exactly obtain the saved trips by enumerating all feasible cooperative cases. For a K-trip cooperative trip set, we propose an exact method to obtain the saved trips by decomposing it to at most K-1 two-trip cooperative trip sets. Computational complexity of the based-on-decomposition exact algorithm is O(N), where N is the total number of trips. Using the based-on-decomposition algorithm, we calculate the exact Shapley value to distribute profit. To empirically verify the exact method, we perform the extensive experiment cases of the real cooperative pickup and delivery service, i.e., "picking up and delivering customers to airport service" (PDCA). (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Cooperation exact algorithm Decomposition Profit distribution exact Shapley value

来源：评论

学校读者我要写书评

暂无评论

Location, pricing and the problem of Apollonius

引用

OPTIMIZATION LETTERS 2017年第8期11卷 1797-1805页

作者： Berger, Andre Grigoriev, Alexander Panin, Artem Winokurow, Andrej Maastricht Univ Dept Quantitat Econ Sch Business & Econ POB 616 NL-6200 MD Maastricht Netherlands Sobolev Inst Math Acad Koptyug Ave 4 Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogov Str Novosibirsk 630090 Russia

In Euclidean plane geometry, Apollonius' problem is to construct a circle in a plane that is tangent to three given circles. We will use a solution to this ancient problem to solve several versions of the following geometric optimization problem. Given is a set of customers located in the plane, each having a demand for a product and a budget. A customer is satisfied if her total, travel and purchase, costs do not exceed the budget. The task is to determine location of production facilities in the plane and one price for the product such that the revenue generated from the satisfied customers is maximized.

关键词： Pricing problem Facility location Apollonius' problem Complexity exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of b-CHROMATIC NUMBER

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 84卷 120-131页

作者： Panolan, Fahad Philip, Geevarghese Saurabh, Saket HBNI Inst Math Sci Madras Tamil Nadu India Chennai Math Inst Madras Tamil Nadu India Univ Bergen Dept Informat N-5020 Bergen Norway

The b-chromatic number of a graph G, chi(b) (G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-CHROMATIC NUMBER problem, the objective is to decide whether X-b(G) >= k. Testing whether Xb(G) = (G) 1, where A(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). We show that b-CHROMATIC NUMBER is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (algorithmica 2013). When k = (G) 1, we design an algorithm for b-CHROMATIC NUMBER running in time 200'2 log k) n ro(i) Finally, we show that b-CHROMATIC NUMBER for an n-vertex graph can be solved in time 0(3nn4logn). (C) 2016 Elsevier Inc. All rights reserved.

关键词： b-Chromatic number exact algorithm Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

algorithms for randomized time-varying knapsack problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期31卷 95-117页

作者： He, Yichao Zhang, Xinlu Li, Wenbin Li, Xiang Wu, Weili Gao, Suogang Shijiazhuang Univ Econ Coll Informat Engn Shijiazhuang 050031 Peoples R China Hebei Normal Univ Coll Math & Informat Sci Shijiazhuang 050024 Peoples R China Shijiazhuang Univ Econ Lab Network & Informat Secur Shijiazhuang 050031 Peoples R China Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming;(2) a 2-approximation algorithm for based on greedy algorithm;(3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis.

关键词： Knapsack problem exact algorithm Approximations Heuristics

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for biological stems search

引用

BMC BIOINFORMATICS 2013年第1期14卷 1-9页

作者： Mi, Tian Rajasekaran, Sanguthevar Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Background: Motifs are significant patterns in DNA, RNA, and protein sequences, which play an important role in biological processes and functions, like identification of open reading frames, RNA transcription, protein binding, etc. Several versions of the motif search problem have been studied in the literature. One such version is called the Planted Motif Search (PMS) or (l, d)-motif Search. PMS is known to be NP complete. The time complexities of most of the planted motif search algorithms depend exponentially on the alphabet size. Recently a new version of the motif search problem has been introduced by Kuksa and Pavlovic. We call this version as the Motif Stems Search (MSS) problem. A motif stem is an l-mer (for some relevant value of l) with some wildcard characters and hence corresponds to a set of l-mers (without wildcards), some of which are (l, d)-motifs. Kuksa and Pavlovic have presented an efficient algorithm to find motif stems for inputs from large alphabets. Ideally, the number of stems output should be as small as possible since the stems form a superset of the motifs. Results: In this paper we propose an efficient algorithm for MSS and evaluate it on both synthetic and real data. This evaluation reveals that our algorithm is much faster than Kuksa and Pavlovic's algorithm. Conclusions: Our MSS algorithm outperforms the algorithm of Kuksa and Pavlovic in terms of the run time as well as the number of stems output. Specifically, the stems output by our algorithm form a proper (and much smaller) subset of the stems output by Kuksa and Pavlovic's algorithm.

关键词： Hash Table exact algorithm Suffix Tree Input String Motif Search

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for the two-dimensional vector packing problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第1期281卷 25-35页

作者： Wei, Lijun Lai, Minghui Lim, Andrew Hu, Qian Nanjing Univ Sch Management & Engn Nanjing 210093 Jiangsu Peoples R China Southeast Univ Sch Econ & Management Nanjing 211189 Jiangsu Peoples R China Natl Univ Singapore Dept Ind Syst Engn & Management Singapore Singapore Guangdong Univ Technol Guangdong Prov Key Lab Comp Integrated Mfg Syst State Key Lab Precis Elect Mfg Technol & Equipmen Guangzhou 510006 Guangdong Peoples R China

The two-dimensional vector packing problem is a well-known generalization of the classical bin packing problem. It considers two attributes for each item and bin. Two capacity constraints must be satisfied in a feasible packing solution for each bin. The objective is to minimize the number of bins used. To compute optimal solutions for the problem, we propose a new branch-and-price algorithm. A goal cut that sets a lower bound to the objective is used. It is effective in speeding up column generation by reducing the number of iterations. To efficiently solve the pricing problem, we develop a branch-and-bound method with dynamic programming, which first eliminates conflicts between two items through branching, and then solves the two-constraint knapsack problem at leaf nodes through dynamic programming. Extensive computational experiments were conducted based on 400 test instances from existing literature. Our algorithm significantly outperformed the existing branch-and-price algorithms. Most of the test instances were solved within just a few seconds. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Packing Two-dimensional vector packing problem exact algorithm Branch-and-price

来源：评论

学校读者我要写书评

暂无评论

An iterative dynamic programming approach for the temporal knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第2期293卷 442-456页

作者： Clautiaux, F. Detienne, B. Guillot, G. Univ Bordeaux UMR CNRS 5251 Inria Bordeaux Sud Ouest Bordeaux France

In this paper, we address the temporal knapsack problem (TKP), a generalization of the classical knapsack problem, where selected items enter and leave the knapsack at fixed dates. We model the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal knapsack exact algorithm Lagrangian relaxation Successive sublimation dynamic programming method

来源：评论

学校读者我要写书评

暂无评论

Computational analysis of a flexible assembly system design problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第3期123卷 453-472页

作者： Kumar, A Jacobson, SH Sewell, EC So Illinois Univ Dept Math & Stat Edwardsville IL 62026 USA Grand Valley State Univ Seidman Sch Business Grand Rapids MI 49504 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

Global competitive priorities are undergoing a marked shift from productivity and quality to flexibility and agility. This has resulted in a growing number of manufacturing companies realizing the importance of building customization capabilities into their production systems. Flexible assembly systems (FASs), consisting of a variety of processors such as assembly, inspection, packaging, and interactive operator consoles, provide a significant opportunity for improving product flexibility and, thereby, gaining sustainable competitive advantage. This paper formulates a decision problem for designing FASs and proves it to be NP-complete. A heuristic, called the pick and rule (PAR) heuristic, is presented to minimize the total number of processors, while determining the number of processors of each type, the sequence of the processors, and the operations to be performed at each processor. A lower bound for the minimum number of processor is derived, and used to assess the effectiveness of the PAR heuristic. An algorithm to compute this bound is also presented. An exact branch and bound algorithm is formulated to find optimal solutions and to provide guidance on the source of the gap between the PAR heuristic and the lower bound results. Computational results with the PAR heuristic, the lower bound algorithm, and the branch and bound algorithm are reported. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： heuristics lower bound algorithm computational analysis complexity branch and bound exact algorithm flexible manufacturing systems flexible assembly systems

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2017年第3期68卷 661-669页

作者： Berger, Andre Grigoriev, Alexander Winokurow, Andrej Maastricht Univ POB 616 NL-6200 MD Maastricht Netherlands

The single facility location problem with demand regions seeks for a facility locationminimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. l(1) or l(infinity). We develop an exact combinatorial algorithm running in time O(n log(c) n) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.

关键词： 1-median Single facility location problem Rectilinear norm Polyhedral norm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On the weak computability of a four dimensional orthogonal packing and time scheduling problem

引用

THEORETICAL COMPUTER SCIENCE 2013年 501卷 1-10页

作者： Huang, Wenqi He, Kun Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

This paper proposes a four dimensional orthogonal packing and time scheduling problem. The problem differs from the classical packing problems in that the position and orientation of each item in the container can be changed over time. In this way, the four dimensional space-time problem better uses the container time. Also, we consider a general case that all parameters are real numbers, which makes the problems more difficult to solve. This paper proposes an algorithm and proves that the algorithm could solve the problem optimally by a finite number of operations. We say this problem is weak computational, meaning that if there exists a universal machine that could represent real numbers and could do unit arithmetic or logical operation on real numbers in finite time, then the algorithm could find optimal solutions in finite time. This paper also presents a proof of the weak computability over a general case of the three dimensional orthogonal packing problem where all parameters are positive real numbers. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Computability exact algorithm Scheduling Higher dimensional packing Real parameters

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：