Improving maritime inventory routing: application to a Brazilian petroleum case

The crude oil offloading and supply problem (COSP) is a type of operation maritime inventory routing (MIR) problem encountered by petroleum companies. In COSP, the company not only is responsible for the ship scheduling to carry the crude oil from production sites to discharge ports but also must maintain inventory levels at both ports (production and consumption) between safety operational bounds to avoid disruptions in its crude oil production and/or refining processes. We show how to improve significantly the decision-making process in a Brazilian petroleum company using a mixed-integer linear programming (MILP) model to represent COSP. Comparison tests with a current ship-scheduling method adopted in the company indicated that the use of the MILP model increased the transportation efficiency and reduced costs by 20% on average. In addition to the quantitative gains, the use of a MILP model to solve COSP has succeeded when encountering real-life events, such as variation in production or consumption rates, berth unavailability, and changes in the storage capacities at ports.     

Order-first split-second methods for vehicle routing problems: A review

Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a giant tour covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has nevertheless led to successful metaheuristics for various vehicle routing problems in the last decade. As many implementations consider an ordering of customers instead of building a giant tour, we propose in this paper the more general name of ordering-first split-second methods. This article shows how this approach can be declined for different vehicle routing problems and reviews the associated literature, with more than 70 references.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

A hybrid optimization-simulation approach for robust weekly aircraft routing and retiming

We address the robust weekly aircraft routing and retiming problem, which requires determining weekly schedules for a heterogeneous fleet that maximizes the aircraft on-time performance, minimizes the total delay, and minimizes the number of delayed passengers. The fleet is required to serve a set of flights having known departure time windows while satisfying maintenance constraints. All flights are subject to random delays that may propagate through the network. We propose to solve this problem using a hybrid optimization-simulation approach based on a novel mixed-integer nonlinear programming model for the robust weekly aircraft maintenance routing problem. For this model, we provide an equivalent mixed-integer linear programming formulation that can be solved using a commercial solver. Furthermore, we describe a Monte-Carlo-based procedure for sequentially adjusting the flight departure times. We perform an extensive computational study using instances obtained from a major international airline, having up to 3387 flights and 164 aircraft, which demonstrates the efficacy of the proposed approach. Using the simulation software SimAir to assess the robustness of the solutions produced by our approach in comparison with that for the original solutions implemented by the airline, we found that on-time performance was improved by 9.8–16.0%, cumulative delay was reduced by 25.4–33.1%, and the number of delayed passengers was reduced by 8.2–51.6%.     

利用改进交叉算子的混合遗传算法求解VRPTW

设计了一种改进的混合遗传算法求解带有时间窗、有车辆重量限制的车辆优化调度问题（VRPTW），根据问题的实际情况，建立了数学模型，提出了改进的交叉算子，丰富了种群的多样性；并结合模拟退火算法的思想，对染色体的适应度适当变化，改善了传统的遗传算法容易“早熟”的缺点，加强了染色体的局部搜索能力。     

具有同时配送和回收需求的车辆路径问题的混合遗传算法

介绍了具有同时配送和回收需求的车辆路径问题(VRPSDP),并对其进行了描述,建立了该问题的数学规划模型。结合2-opt法和等级替换策略等设计了求解VRPSDP的一种混合遗传算法,给出了该算法初始种群的两种生成规则———随机生成和构造初始种群,设计了相应的交叉和变异算子,并详细阐述了违反约束条件的处理方法。通过随机模拟试验以及与其他方法的对比分析表明:该算法可有效缩短车辆行驶距离,而构造初始种群则在一定条件下可显著提高混合遗传算法的收敛速度并改善其运行结果。     

绿化修剪车避障工作装置运动学分析

以绿化修剪车的工作装置为研究对象,通过矩阵分析法建立了工作臂矢量运动方程,完成了机械臂的运动学分析。同时,运用ADAMS对绿化修剪车的工作装置进行了运动学仿真,得到了绿化修剪车触杆的运动包络图和割草机触杆末端的位移、速度及加速度,验证了机械臂数学模型的正确性。最后,根据绿化修剪车工作装置的实际运动情况和仿真结果,推算出绿化修剪车的最大作业速度和避障时间,为后续液压系统设计和工作臂的控制设计提供了理论依据。     

Piecewise affine control for lane departure avoidance

This article presents the design of a lane departure avoidance system which is conceived to operate even in demanding manoeuvres with respect to the lateral vehicle dynamics. Piecewise affine state feedback and output feedback controllers are used to handle the nonlinear behaviour of the lateral tyre forces. The controllers are designed based on the search of a piecewise quadratic Lyapunov function casted as a bilinear matrix inequalities problem. Experimental tests demonstrate the performance of the controller in degraded road conditions.     

餐饮物流配送路线的优化研究

近年来,我国的餐饮企业迅速发展壮大,随之而来的问题是如何控制物流配送成本,合理的配送规划将直接影响一个企业的成本控制、效率和竞争能力。针对餐饮业的特点提出一个规划方案:按货物品种来确定配送节点的方法,并以此为基础,分别从选择配送点和对路线变更方案进行了研究。最后的算例将提出的总成本概念应用到用最短路径方法中来求解最优路径,表明全面的成本概念在配送规划中的重要作用。     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.