Mining fleet management systems: a review of models and algorithms

The objective of this paper is to review and document the mine fleet management systems’ models and algorithms. The purpose is to understand the algorithms behind the fleet management systems and the proposed academic solutions in this area to identify any gaps in the current literature and to open up opportunities to establish research questions that need to be addressed in an integrated simulation and optimisation operational planning research framework. In this paper, we review industrial fleet management systems and the main academic algorithms behind such systems. The fleet management systems are divided into three subsequently related problems to review: shortest path, production optimisation and real-time dispatching. Finally, the limitations of current algorithms for fleet management systems are documented in terms of mining practice feasibility and optimality of the solution on large-scale problems. The results of this literature review enable us to evaluate the logical links between major components of an integrated simulation and optimisation operational planning framework with current theory of fleet management systems.     

多时空配送任务驱动的无人车队车辆数优化方法

为解决快递终端配送多时空任务驱动下的最小无人车队车辆数配置问题,提出一种随机优化方法。首先,分析服务时长和等待时长对无人车队行驶路线规划的影响,从而构建最短路径模型;然后,基于二维时空网络构造服务序列网络;其次,通过网络转换将最小无人车队车辆数配置问题转化为网络最大流问题,并建立以车队车辆数最小为目标的最小车队模型;最后,针对模型特征设计一种融合Dijkstra算法和Dinic算法的Dijkstra-Dinic算法来对最小无人车队车辆数配置问题进行求解。在四种不同规模的服务网络中进行仿真实验,实验结果表明：在不同成功服务率下,最小无人车队车辆数与服务网络规模呈正相关,但随等待时长的增加而减少并趋向于稳定;所提算法中所引入的One-stop算子大大提高了搜索效率,所提模型和算法适用于大规模服务网络中的最小车队计算。     

A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows

This paper presents a hybrid evolutionary algorithm (HEA) to solve heterogeneous fleet vehicle routing problems with time windows. There are two main types of such problems, namely the fleet size and mix vehicle routing problem with time windows (F) and the heterogeneous fixed fleet vehicle routing problem with time windows (H), where the latter, in contrast to the former, assumes a limited availability of vehicles. The main objective is to minimize the fixed vehicle cost and the distribution cost, where the latter can be defined with respect to en-route time (T) or distance (D). The proposed unified algorithm is able to solve the four variants of heterogeneous fleet routing problem, called FT, FD, HT and HD, where the last variant is new. The HEA successfully combines several metaheuristics and offers a number of new advanced efficient procedures tailored to handle the heterogeneous fleet dimension. Extensive computational experiments on benchmark instances have shown that the HEA is highly effective on FT, FD and HT. In particular, out of the 360 instances we obtained 75 new best solutions and matched 102 within reasonable computational times. New benchmark results on HD are also presented.     

基于复杂网络的舰艇作战模型研究

借鉴复杂网络的作战描述模型,把作战单元抽象成节点,把各单元之间的相互作用抽象成有向边,将战场描述为1个由传感器、决策器、影响器、目标4类节点组成的有向网络图,构建了1个基于复杂网络的舰艇网络模型,在模型中将单个舰艇作战和舰艇编队作战进行了比较。应用复杂网络的若干特征参数分别对几个舰艇和舰艇编队的作战网络效能进行了仿真分析。通过仿真结果的对比,说明舰艇进行编队时,指挥体系连通性的提高能够大大提高舰艇编队的作战效能     

三峡-葛洲坝两坝间现行船队通航流量适应能力研究

三峡—葛洲坝两坝间河道通航难点段诸多,河道蜿蜒曲折,沟壑浅滩水流紊乱,并存在泡漩等不利的险恶流态,给船舶(队)的航行安全带来隐患。介绍了5套运行较多、具有代表性的船舶(队),在两坝间来流量45 000～35 000 m3/s时进行的通航船模试验成果。在来流量40 000 m3/s以下,各船队可通过两坝间各困难航段,其航行指标基本满足船队安全航行的要求,500 t以下的各小型船队应限定在来流量35 000 m3/s以下航行,较为安全;两坝间河道的6个困难航段中,上行较难的为喜滩和狮子垴段,居中为莲沱段、其次为石牌、偏垴和南津关段。该研究成果对今后两坝间行船有一定的实用价值和指导意义。     

A study of replacement rules for a parallel fleet replacement problem based on user preference utilization pattern and alternative fuel considerations

Parallel fleet replacement problems deal with determining an optimal replacement schedule that results in a minimal total cost of owning and operating a fleet within a finite planning horizon. In this paper, the fleet consists of service vehicles, varying in age and cumulative mileage, commonly owned by government agencies or private business organizations. The paper focuses on three main aspects of the problem, including the effects of some widely used replacement rules, consideration of alternative fuel vehicles for replacement, and a new “user preference” utilization pattern. The vehicle replacement rules under study include purchase-new-vehicles-only, no-splitting-in-selling, one-purchase-choice, older-vehicles-selling, and all-or-none rules. The initial fleet consists of gasoline vehicles, while alternative-fuel vehicles using either compressed natural gas (CNG) or liquefied petroleum gas (LPG) are included as challengers in every replacement decision period. The user preference utilization pattern denotes a pattern in which yearly usage of vehicles declines as the vehicles grow older or have higher cumulative mileage. Integer programming formulation of the defined problem that incorporates these new factors is provided. Small numerical examples under various scenarios and a large problem instance with model parameters estimated from actual data are solved to optimality to gain some insights about the replacement rules and other considered factors.     

机群更换部件使用保障过程仿真

研究费用与机群完好率之间的关系一直是备件保障研究的中心问题，此问题最终归结于研究备件库存种类与数量对机群完好率的影响。该文通过研究飞机可更换部件的使用与保障过程，建立其使用保障过程模型，并通过仿真模拟可更换部件的消耗过程。目的在于寻求可更换部件缺航材率与机群完好率指标之间的关系，为机群在未来一段时间内备件的库存水平决策提供支持。最后通过一个实例介绍如何通过仿真建立机群完好率与部件缺航材率的函数关系。     

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.     

A reconfiguration of fire station and fleet locations for the Santiago Fire Department

The geographical distribution of the population of the city of Santiago, Chile, has changed significantly in recent years. In spite of this fact, the location of the fire stations has remained unchanged. We propose a model for the optimal location of the fire stations and a fleet assignment for the Santiago Fire Department (SFD), aimed at maximising the number of events attended to with a predefined standard response. The results of the model are compared with respect to the current location of fire stations and fleet assignment in the SFD. There are different types of resources (stations and vehicles), and different types of events in which the same types of vehicles are used. We analyse various possible current and future scenarios, using a forecast based on historical data. Our results show that by optimally reallocating the resources a 10–30% increase can be achieved in the number of emergency calls that are attended to with an adequate response in time and number of vehicles, without the need for additional fire stations or vehicles. Thus our contribution is empirical and relies on the real world application which is being considered by Chilean government.     

A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.