求解复杂有时间窗装卸货问题的遗传算法

有时间窗装卸货问题是为一个车队安排最优的服务路径以满足客户的运输需求,每个客户的装卸货任务由一辆车完成,即在该客户的装货点装载一定数量的货物后运往该客户的卸货点,所有任务的完成必须满足车辆的容量约束、行程约束和客户装卸货点的时间窗约束。从多车库、多货物类型和满载三个方面对一般有时间窗装卸问题（PDPTW）进行了扩展,提出一种解决复杂PDPTW问题的遗传算法,实验结果表明,该算法能有效解决复杂PDPTW问题,并取得较好的优化结果。     

A generalized exchange heuristic for the capacitated vehicle routing problem

We consider the problem of dispatching the minimum number of vehicles from a central depot to make deliveries to a set of clients with known demands. The objective is to minimize the total distance travelled, subject to vehicle capacity requirements. We present a new heuristic algorithm for solving this problem. The algorithm is based on generalized edge-exchange search procedures, and relaxation of the capacity requirements. Computational results, based upon standard test problems with up to 249 customers, indicate that our heuristic compares favourably with known heuristics in terms of solution quality.     

A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows

The Capacitated Vehicle Routing Problem with Time Windows (VRPTW) consists in determining the routes of a given number of vehicles with identical capacity stationed at a central depot which are used to supply the demands of a set of customers within certain time windows. This is a complex multi-constrained problem with industrial, economic, and environmental implications that has been widely analyzed in the past. This paper deals with a multi-objective variant of the VRPTW that simultaneously minimizes the travelled distance and the imbalance of the routes. This imbalance is analyzed from two perspectives: the imbalance in the distances travelled by the vehicles, and the imbalance in the loads delivered by them. A multi-objective procedure based on Simulated Annealing, the Multiple Temperature Pareto Simulated Annealing (MT-PSA), is proposed in this paper to cope with these multi-objective formulations of the VRPTW. The procedure MT-PSA and an island-based parallel version of MT-PSA have been evaluated and compared with, respectively, sequential and island-based parallel implementations of SPEA2. Computational results obtained on Solomon’s benchmark problems show that the island-based parallelization produces Pareto-fronts of higher quality that those obtained by the sequential versions without increasing the computational cost, while also producing significant reduction in the runtimes while maintaining solution quality. More specifically, for the most part, our procedure MT-PSA outperforms SPEA2 in the benchmarks here considered, with respect to the solution quality and execution time.     

A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups

A well-known variant of the vehicle routing problem involves backhauls, where vehicles deliver goods from a depot to linehaul customers and pick up goods from backhaul customers to the depot. The vehicle routing problem with divisible deliveries and pickups (VRPDDP) allows vehicles to visit each client once or twice for deliveries or pickups. In this study, a very efficient parallel approach based on variable neighborhood search (VNS) is proposed to solve VRPDDP. In this approach, asynchronous cooperation with a centralized information exchange strategy is used for parallelization of the VNS approach, called cooperative VNS (CVNS). All available problem sets of VRPDDP have been successfully solved with the CVNS, and the best solutions available in the literature have been significantly improved.     

Cross-docking and milk run logistics in a consolidation network: A hybrid of harmony search and simulated annealing approach

In this paper, we develop a novel integer programming model for the transportation problem of a consolidation network where a set of vehicles are used to transport goods from suppliers to their corresponding customers via three transportation systems: direct shipment, shipment through cross-dock (indirect shipment) and milk run. Since the proposed problem formulation is NP-hard, we offer a hybrid of harmony search (HS) and simulated annealing (SA) based heuristics (HS-SA algorithm) in order to solve the problem. The objective of this problem is to minimize the total shipping cost in the network, so it is tried to reduce the number of required vehicles using an efficient vehicle routing strategy in the algorithm. Solving several numerical examples demonstrates that our solving approach performs much better than GAMS/CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for large size problem instances.     

Vehicle routing with pick-up and delivery: tour-partitioning heuristics

Many applications of the classical vehicle routing problem involve pick-up and delivery services between the depot and peripheral locations (warehouses, stores, stations). This paper studies an important version of the vehicle routing problem with pick-up and delivery (the so-called delivery and backhaul problem): delivery in our case refers to transportation of goods from the depot to customers, and pick-up (backhaul) refers to shipment from customers to the depot. The objective is to find a set of vehicle routes that service customers such that vehicle capacity is not violated and the total distance traveled is minimized. Tour partitioning heuristics for solving the capacitated vehicle routing problem are based on breaking a basic tour into disjoint segments served by different vehicles. This idea is adapted for solving the delivery and backhaul problem. Two heuristics that focus on efficient utilization of vehicles’ capacities are introduced, analyzed and tested numerically.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

三维装载与CVRP 联合多目标优化问题的模型及算法

提出三维装载与CVRP联合多目标优化问题(3LCVRPMO)模型,该模型在三维装载约束下的CVRP问题(3LCVRP)的基础上,考虑了配送车辆数目及路径总距离两个目标函数.在权衡装箱和路径优化两个优化过程的基础上,构建了多阶段/两层混合算法架构(MSOTLH)及其算法,并对路径优化偏好的3LCVRPMO问题进行求解.基于3LCVRP问题相关算例的数据实验结果表明,所提出的3LCVRPMO模型及MSOTLH算法是有效的.     

混合动力电动汽车的跟车控制与能量管理

混合动力电动汽车(Hybrid electric vehicles, HEVs)的能量管理问题至关重要, 而混合动力电动汽车的跟车控制不仅涉及跟车效果与安全性, 也影响着能量的高效利用. 将HEVs的跟车控制与能量管理相结合, 提出一种基于安全距离的HEVs车辆跟踪与能量管理控制方法. 首先, 考虑坡度、载荷变动建立了HEVs车辆跟车系统的非线性模型, 并基于安全距离, 提出一种基于道路观测器的动态面控制(Dynamic surface control, DSC)进行车辆跟踪控制. 然后, 结合跟踪控制下工况循环, 采用滚动动态规划(Dynamic programming, DP)算法进行混合动力电动汽车能量实时优化控制. 最后, 通过仿真研究进行验证.     

求解k中间点问题的新局部搜索算法

为有效求解大规模k中间点问题,利用适应度距离相关性方法分析,发现该问题局部最优解的适应度与其到全局最优解的距离无太大关系,且多个局部最优解求交所得子集以极大概率包含全局最优解中的元素,进而提出一种基于求交操作的k中间点问题局部搜索算法。实验结果表明该算法在求解质量上与目前已知算法相比有较大改进。     

OVRP_GELS: solving open vehicle routing problem using the gravitational emulation local search algorithm

In open vehicle routing problem (OVRP), after delivering service to the last customer, the vehicle does not necessarily return to the initial depot. This type of problem originally defined about thirty years ago and still is an open issue. In real life, the OVRP is similar to the delivering newspapers and consignments. The problem of service delivering to a set of customers is a particular open VRP with an identical fleet for transporting vehicles that do not necessarily return to the initial depot. Contractors which are not the employee of the delivery company use their own vehicles and do not return to the depot. Solving the OVRP means to optimize the number of vehicles, the traveling distance and the traveling time of a vehicle. In time, several algorithms such as tabu search, deterministic annealing and neighborhood search were used for solving the OVRP. In this paper, a new combinatorial algorithm named OVRP_GELS based on gravitational emulation local search algorithm for solving the OVRP is proposed. We also used record-to-record algorithm to improve the results of the GELS. Several numerical experiments show a good performance of the proposed method for solving the OVRP when compared with existing techniques.

     

基于时空网络的自动化集装箱码头自动化导引车路径规划

针对自动化集装箱码头水平搬运作业中自动化导引车路径冲突问题,提出一种基于时空网络的路径优化方法。对于单个运输需求,首先,将路网离散化为网格网络,设计依据时间可更新的时空网络;其次,以任务完工时间最短为目标,基于时空网络下可用路段集合来建立车辆路径优化模型;最后,在时空网络上运用最短路径算法求解得最短路径。对于多个运输需求,为避免路径冲突,根据当前运输需求的路径规划结果更新下一个运输需求的时空网络,并通过迭代最终获得满足规避碰撞和缓解拥堵条件的路径规划。计算实验中,与基本最短路径求解策略（求解算法P）相比,所提方法的碰撞次数降低为0并且最小相对距离始终大于安全距离;与停车等待求解策略（求解算法SP）相比,所提方法最多减少任务总延误时间24　s,且明显降低延误任务占比以及路网平均拥堵度,最大降低程度分别为2.25%和0.68%。实验结果表明,所提方法能够有效求解大规模冲突规避的路径规划问题,并显著提高自动化导引车的作业效率。     

Error concealment algorithm based on sparse optimization

In this paper, an application of sparse optimization in the error concealment area is proposed. The spatial and temporal formulations of the pixels in the current frame and reference frame are proposed to solve the problem. Based on the sparse characteristics of nature images, we form sparse optimization problems for both formulations. The optimization problem is solved by the primal-dual interior point method. The solutions are combined for better results. By solving for a limited numbers of significant predictors using the sparse optimization, our algorithm performs subjectively and objectively better for the concealed result; compared to two state-of-the-art spatial-temporal hybrid error concealment methods, the proposed methods can improve by up to 0.19 dB and 1.12 dB in PSNR (Peak Signal-to-Noise Ratio).     

An effective tabu search approach with improved loading algorithms for the 3L-CVRP

In this paper, we consider the Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines the routing of a fleet of vehicles and the loading of three-dimensional shaped goods into the vehicles while minimizing the total travel distance incurred. Apparently, 3L-CVRP is a combination of capacitated vehicle routing and three-dimensional bin packing problem and thus of high complexity. Different from most of previous works, we propose an innovative approach, called improved least waste heuristic for solving the loading subproblem, which is iteratively invoked by a simple tabu search algorithm for the routing. The good performance in terms of the solution quality and computational efficiency of our approach is shown through the numerical experiments on the benchmark instances from literature.     

A computational comparison of several models for the exact solution of the capacity and distance constrained plant location problem

The Capacity and Distance Constrained Plant Location Problem is an extension of the discrete capacitated plant location problem, where the customers assigned to each plant have to be assigned to vehicles. In addition to the capacity constraints on the plants, there is a limit on the total distance traveled by each vehicle to serve its assigned customers by means of round trips. This paper presents several formulations for the problem and proposes different families of valid inequalities. The results of extensive computational experiments are presented and analyzed.     

Site dependent vehicle routing problem with soft time window: Modeling and solution approach

This paper presents two meta-heuristic algorithms, an ant colony system with local searches and a tabu search algorithm, for Site-Dependent Vehicle Routing Problem with Soft Time Window (SDVRPSTW). In the SDVRPSTW a fleet of vehicles must deliver goods to their allowable set of customers, preferably in their time windows while the capacity constraints of the vehicles must be respected. Based on our best knowledge, this problem which challenges the distribution task of public services and private organizations in an urban context with heavy traffic has not yet been considered in practical aspects, especially where the vehicles entrance to some areas needs traffic license. Hence, in addition to present an Integer Linear Programming (ILP) model, we present the two mentioned algorithms to handle the problem in large scale instances. Furthermore, the algorithms efficiency and their optimality are analyzed by experimental results both in small and large dimensions.     

A novel learning based approach for a new integrated location-routing and scheduling problem within cross-docking considering direct shipment

One of the most important problem in supply chain management is the design of distribution systems which can reduce the transportation costs and meet the customer's demand at the minimum time. In recent years, cross-docking (CD) centers have been considered as the place that reduces the transportation and inventory costs. Meanwhile, neglecting the optimum location of the centers and the optimum routing and scheduling of the vehicles mislead the optimization process to local optima. Accordingly, in this research, the integrated vehicle routing and scheduling problem in cross-docking systems is modeled. In this new model, the direct shipment from the manufacturers to the customers is also included. Besides, the vehicles are assigned to the cross-dock doors with lower cost. Next, to solve the model, a novel machine-learning-based heuristic method (MLBM) is developed, in which the customers, manufacturers and locations of the cross-docking centers are grouped through a bi-clustering approach. In fact, the MLBM is a filter based learning method that has three stages including customer clustering through a modified bi-clustering method, sub-problems’ modeling and solving the whole model. In addition, for solving the scheduling problem of vehicles in cross-docking system, this paper proposes exact solution as well as genetic algorithm (GA). GA is also adapted for large-scale problems in which exact methods are not efficient. Furthermore, the parameters of the proposed GA are tuned via the Taguchi method. Finally, for validating the proposed model, several benchmark problems from literature are selected and modified according to new introduced assumptions in the base models. Different statistical analysis methods are implemented to assess the performance of the proposed algorithms.     

基于混合优化算法的网络流量有效测量点选择

提出一种基于禁忌搜索和蚁群算法的求解最小弱顶点覆盖问题的混合优化算法,用于解决网络流量有效测量点的选择问题。仿真结果表明,比较现有算法,本算法能够找到更小的弱顶点覆盖集,且具有更好的可扩展性和实用性。     

模糊环境下的最小权顶点覆盖问题*

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。     

考虑用户选择偏好的电动汽车充电站规划研究

在国家大力发展新能源汽车的过程中,充电问题一直阻碍着电动汽车的发展,充电基础设施尤其是快速充电站的规划和建设尤为重要。大规模发展电动汽车（electric vehicle,EV）的关键是根据用户的充电选择偏好,建立完善的充电基础设施,减少用户的里程焦虑,彻底解决充电不方便的问题。在考虑了各方面社会因素并确定一定数量的候选节点背景研究的基础上,提出了一种双目标规划模型,在满足需求、距离、容量等约束条件下,分析了建设充电站总成本和充电覆盖范围之间的关系,寻找最优的充电站建设方案,并以A城市B区为例,通过多目标粒子群算法进行求解,求出充电站的最佳节点和数量。用不同算法进行求解,通过对结果进行分析比较,表明多目标粒子群算法（MOPSO）在求解双目标问题时更具有实际意义。