Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem

Multi Compartment Vehicle Routing Problem is an extension of the classical Capacitated Vehicle Routing Problem where different products are transported together in one vehicle with multiple compartments. Products are stored in different compartments because they cannot be mixed together due to differences in their individual characteristics. The problem is encountered in many industries such as delivery of food and grocery, garbage collection, marine vessels, etc. We propose a hybridized algorithm which combines local search with an existent ant colony algorithm to solve the problem. Computational experiments are performed on new generated benchmark problem instances. An existing ant colony algorithm and the proposed hybridized ant colony algorithm are compared. It was found that the proposed ant colony algorithm gives better results as compared to the existing ant colony algorithm.     

考虑布线资源松弛的X结构Steiner最小树算法

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构Steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.     

Heuristic approach for solving employee bus routes in a large-scale industrial factory

This paper compares different methods for solving a location-routing problem (LRP), using real-world data from the bus transport service for employees of a large-scale industrial factory in Thailand. We tested four AI (artificial intelligence) techniques Maximin, K-means, Fuzzy C-means, and Competitive Learning and two hybrids of these four K-means with Competitive Learning and K-means with Maximin to allocate the bus stops. The efficiency of the algorithms was compared, in terms of the quality of the solutions. The K-means with Maximin provided the best solution, as it minimized number of bus stop locations and employees’ total traveling distance while satisfied employee at maximum radius 1.73 km, compared to K-means with Competitive Learning, as the same number of bus stop it provided higher total traveling distance and maximum radius. The other non-hybrid techniques provided higher number of bus stop locations.We then used ant colony optimization (ACO) to determine the optimal routing between the 300–700 bus stops as allocated by K-means with Maximin. The optimal bus routing to transport the factory’s 5000 plus employees required 134 buses (134 independent routes) covering 500 bus stops and traveling nearly 5000 km. While optimal, this routing was costly and created monitoring difficulties. To address these concerns, we constrained the number of bus routes; while this dramatically increased the total distance, it provided a more practical solution for the factory.     

变邻域量子烟花算法求解CVRP

针对带容量约束的车辆路径问题，提出一种融合量子进化算法和变邻域优化策略的变邻域量子烟花算法。该算法采用等分随机键与最大位置法结合的实数编码方式，通过量子旋转门和非门变异提高算法全局搜索能力，同时运用结合2-Opt的变邻域优化策略加强局部搜索能力。选取17个基准算例进行参数实验和对比实验，实验结果表明，相对于对比算法，所提出的算法具有较好的寻优能力和收敛速度。     

Efficient approximation algorithms for the routing open shop problem

We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.     

一种基于PMP方式的多跳无线网络结构

针对ad-hoc网络的规模效应问题,提出了一种基于PMP方式的多跳网络结构,并且介绍此网络结构的使用方式,同时进行特点分析及比较。最后给出路由算法实现了自动组网、自动选举树根的功能,使得系统使用更加简便。     

Cooperative schemes for path establishment in mobile ad-hoc networks under shadow-fading

The performance of routing protocols for multi-hop path-establishment in Mobile Ad-hoc NETworks (MANET) is examined when the individual radio links undergo shadow fading of parameterized severity. Such propagation modeling is typical of ground-level networking along with node mobility. The metrics of main interest are the probability of having a reliable multi-hop path plus the temporal statistics of such availability under a Markovian model. Such availability is an indicator for the suitability of the network to carry delay-sensitive applications (push-to-talk voice, streaming video) in uninterrupted manner. It is shown that high levels of diversity are necessary in such adverse environments, as obtained either by multiple independent paths or via concurrent cooperative transmission. Analytical and simulation comparisons of typical routing options are presented on the above metrics, plus on the required nodal engagement for supporting such diversity.     

Enhanced exact solution methods for the Team Orienteering Problem

The Team Orienteering Problem (TOP) is one of the most investigated problems in the family of vehicle routing problems with profits. In this paper, we propose a Branch-and-Price approach to find proven optimal solutions to TOP. The pricing sub-problem is solved by a bounded bidirectional dynamic programming algorithm with decremental state space relaxation featuring a two-phase dominance rule relaxation. The new method is able to close 17 previously unsolved benchmark instances. In addition, we propose a Branch-and-Cut-and-Price approach using subset-row inequalities and show the effectiveness of these cuts in solving TOP.     

Constructive heuristics for the Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities

The Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities (MCARPTIF) is an extension of the Arc Routing Problem under Capacity and Length Restrictions with Intermediate Facilities (CLARPIF) with application in municipal waste collection. This paper evaluates four constructive heuristics capable of computing feasible solutions for the MCARPTIF with a primary objective to either minimise total cost or to minimise the fleet size. The heuristics were adapted from Path-Scanning and Improved-Merge for the Mixed Capacitated Arc Routing Problem, and compared against two Route-First-Cluster-Second heuristics for the MCARPTIF. The objective was to identify the best performing heuristic for application purposes. In practice, the CARP is often solved for real-time or near real-time decision support. Computational time required by the heuristics was thus also evaluated. Identifying the best heuristic proved difficult due to a lack of realistic MCARPTIF benchmark sets, with the two CLARPIF sets predominantly solved in the literature not resembling actual waste collection instances. Route-First-Cluster-Second heuristics, linked with a new vehicle reduction heuristic performed the worst on the two CLARPIF sets, yet performed the best on new waste collection sets taken from the literature and introduced in this paper. Improved-Merge performed the best on two existing CLARPIF sets and on a realistic set with Intermediate-Facilities incident with the vehicle depot, but struggled on all other sets and in minimising fleet size. Path-Scanning was the most robust heuristic, performing reasonably well on all benchmark sets and both objectives. Results further show that due to the high computational time of one of the Route-First-Cluster-Second heuristics, which was only exposed on realistically sized sets, the slightly worse version is the best alternative when real-time support is required for waste collection applications.