带软时间窗的多车场开放式车辆调度

带软时间窗的多车场开放式车辆调度问题是在开放式车辆路径问题的基础上,考虑了多车场和客户服务时间的约束,是一类典型的NP难解问题。针对该问题,提出了一种改进的蚁群算法求解方案,并建立了相应的数学模型。首先通过设置一个虚拟车场将多车场VRP转化为单车场VRP,然后利用参数控制的改进蚁群算法与2-opt算法结合来对模型求解。算法先利用K-means与细菌觅食算法相结合的聚类技术判断蚁群状态,进而动态调整算法参数,使其快速收敛到全局最优解附近,再依据混沌理论的特点来调整参数,使其跳出局部最优。最后,再利用2-opt算法对最优解进行优化。实验结果验证了该算法求解MDOVRPSTW问题的有效性。     

MDVRPTW问题多阶段迭代启发式算法

提出一个求解多车库VRPTW问题的聚类和迭代混合遗传算法。该算法采用三阶段过程：客户聚类分配、路径规划和路径改进,与以往两阶段算法不同,该算法采用混合遗传算法进行路径规划,采用竞争-插入进行路径改进,且路径规划与路径改进有机结合形成迭代路径规划过程。用Cordeau等人提出的算例实验表明该算法能够在可以接受的计算时间内得到可接受的好解。     

Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm

This paper presents a new model and solution for multi-objective vehicle routing problem with time windows (VRPTW) using goal programming and genetic algorithm that in which decision maker specifies optimistic aspiration levels to the objectives and deviations from those aspirations are minimized. VRPTW involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. This paper uses a direct interpretation of the VRPTW as a multi-objective problem where both the total required fleet size and total traveling distance are minimized while capacity and time windows constraints are secured. The present work aims at using a goal programming approach for the formulation of the problem and an adapted efficient genetic algorithm to solve it. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search and the concept of Pareto optimality for the multi-objective optimization. Moreover part of initial population is initialized randomly and part is initialized using Push Forward Insertion Heuristic and λ-interchange mechanism. The algorithm is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances. Results show that the suggested approach is quiet effective, as it provides solutions that are competitive with the best known in the literature.     

多配送中心粮食物流车辆调度混合蚁群算法

在对多配送中心粮食车辆调度问题进行直观描述的基础上,建立了该问题的数学模型。并在国内外研究现状的基础上,提出了一个混合蚁群算法来求解多配送中心车辆调度问题,设计了蚂蚁转移策略、可行解构造策略和信息素更新策略,采用K邻域来限制蚂蚁的转移目标,并采用LK算法优化策略来优化蚂蚁遍历路径和可行解。给出了一个具有代表性的算例实验结果和结果分析,通过实验表明了此方法对优化多配送中心粮食车辆调度问题的有效性。     

时变路网下带混合时间窗的车辆路径问题

针对时变路网下带混合时间窗的车辆路径问题,综合考虑多中心联合配送、混合时间窗、车辆行驶速度连续变化及车辆行驶速度、载重量对油耗的影响,以车辆派遣成本、油耗成本及时间窗惩罚成本之和最小为目标建立优化模型,并设计自适应遗传-大邻域搜索算法对其进行求解。该算法采用自适应交叉、变异以加快种群寻优速度,并引入时差插入法改进交叉算子和变异算子,嵌入移除算子和插入算子对可行解进行摧毁和重建以增加种群的多样性。通过多组算例验证算法的有效性,并分析了混合时间窗客户的比例变化及车辆行驶速度变化对车辆调度方案的影响,结果表明自适应遗传-大邻域搜索算法较基本算法有着更好的求解性能。该研究成果可丰富车辆路径问题的相关研究,为物流企业优化决策配送方案提供理论依据。     

带时间窗的多车场车辆路径优化的粒子群算法

带时间窗的多车场车辆路径问题在基本车辆路径问题的基础上增加了“多车场”与“时间窗”两个约束条件,是一个典型的NP难解问题。将粒子群算法应用于带时间窗的多车场车辆路径优化问题,构造了一种适用于求解车辆路径问题的粒子编码方法,建立了相应的数学模型,在此基础上设计了相应的算法。算例通过和遗传算法、蚁群算法进行比较,证明了其搜索速度和寻优能力的优越性。     

Multi-depot vehicle routing problem: a one-stage approach

This paper introduces multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD) which is one important and useful variant of the traditional multi-depot vehicle routing problem (MDVRP) in the supply chain management and transportation studies. After modeling the MDVRPFD as a binary programming problem, we propose two solution methodologies: two-stage and one-stage approaches. The two-stage approach decomposes the MDVRPFD into two independent subproblems, assignment and routing, and solves them separately. In contrast, the one-stage approach integrates the assignment with the routing where there are two kinds of routing methods-draft routing and detail routing. Experimental results show that our new one-stage algorithm outperforms the published methods. Note to Practitioners-This work is based on several consultancy work that we have done for transportation companies in Hong Kong. The multi-depot vehicle routing problem (MDVRP) is one of the core optimization problems in transportation, logistics, and supply chain management, which minimizes the total travel distance (the major factor of total transportation cost) among a number of given depots. However, in real practice, the MDVRP is not reliable because of the assumption that there have unlimited number of vehicles available in each depot. In this paper, we propose a new useful variant of the MDVRP, namely multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD), to model the practicable cases in applications. Two-stage and one-stage solution algorithms are also proposed. The industry participators can apply our new one-stage algorithm to solve the MDVRPFD directly and efficiently. Moreover, our one-stage solution framework allows users to smoothly add new specified constraints or variants.     

带软时间窗的开放式满载车辆路径问题研究

为满足某些生产制造企业的满载运输需求,针对运输任务对车辆具有独占性的特点,分析得到总运输费用的大小取决于车辆的空车行驶费用,在此基础上,将带软时间窗的开放式满载车辆路径问题转化为带软时间窗的多车场开放式车辆路径问题,在非对称图上建立了相应的数学模型,并设计了近邻粒子群算法对模型进行求解。设计算例对算法进行了验证,实验结果表明：该算法可以快速求得软时间窗的开放式满载车辆路径问题的满意解。     

Discrete firefly algorithm with compound neighborhoods for asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery

We introduce a new variant of the vehicle routing problem, that is, the asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery. When providing door-to-door service for farm machinery maintenance, there exists not only node service, (e.g., part replacement), but also directed arc service, (e.g., pulling the breakdown farm machinery from the farm location to the specified maintenance station). In the problem, there are multiple constraints, including the customer’s time window, maximum repairman working duration, fleet size, and vehicle capacity, etc. A mathematical programming model is formulated with the minimum total costs by transforming the problem into the asymmetric multi-depot vehicle routing problem with time windows. Discrete firefly algorithm with compound neighborhoods, presenting new neighborhood methods, is proposed to solve it. New procedures to evaluate the duration infeasibility are suggested with the reduced additional computational complexity. Computational results demonstrate that the proposed approach performs better than CPLEX solver, especially for large designed instances. Moreover, the proposed approach is superior to the other algorithms on solving benchmark instances of multi-depot vehicle routing problem with time windows. This study can provide decision support to door-to-door service for the maintenance of farm machinery.     

The vehicle routing problem with multiple prioritized time windows: A case study

This paper addresses Multi-objective Vehicle Routing Problem with Multiple Prioritized Time Windows (VRPMPTW) in which the distributer proposes a set of all non-overlapping time windows with equal or different lengths and the customers prioritize these delivery time windows. VRPMPTW aims to find a set of routes of minimal total traveling cost and maximal customer satisfaction (with regard to the prioritized time windows), starting and ending at the depot, in such a way that each customer is visited by one vehicle given the capacity of the vehicle to satisfy a specific demand. This problem is inspired from a real life application. The contribution of this paper lies in its addressing the VRPMPTW from a problem definition, modeling and methodological point of view. We developed a mathematical model for this problem. This model can simply be used for a wide range of applications where the customers have multiple flexible time windows and violation of time windows may drop the satisfaction levels of customers and lead to profit loss in the long term. A Cooperative Coevolutionary Multi-objective Quantum-Genetic Algorithm (CCMQGA) is also proposed to solve this problem. A new local search is designed and used in CCMQGA to reach an appropriate pareto front. Finally, the proposed approach is employed in a real case study and the results of the proposed CCMQGA are compared with the current solution obtained from managerial experience, the results of NSGA-II and the multi-objective quantum-inspired evolutionary algorithm.     

战时备件配送的MDVRP问题及其遗传算法求解

战时备件配送的车辆调度是提高装备保障效率的关键因素。以装备战斗效能损失最小化为车辆调度的目标,建立了多仓库车辆路径问题MDVRP（Multi—Depot Vehicle Routing Problem）模型,并应用混合遗传算法对问题进行了求解。算法中,设计了串行、并行及半并行三种交叉算子,并应用局部搜索模块对子个体进行改进。对算例的计算实验表明,半并行交叉算子在精度方面优于另外两种交叉算子。     

多中心半开放式送取需求可拆分的车辆路径优化

针对多中心半开放式送取需求可拆分的车辆路径问题,构建了以车辆配送距离最短为目标的多中心半开放式送取需求可拆分的数学模型。设计大变异邻域遗传算法进行求解,采用二维染色体编码及顺序交叉策略,同时运用大变异策略和邻域搜索策略提高算法全局和局部的寻优能力,通过算例对比验证了所提模型与算法的有效性。算例实验表明,大变异邻域遗传算法在求解多中心物流配送车辆路径问题上求解质量较优、求解效率较高、求解结果较为稳定,同时验证了联合配送下多中心半开放式送取需求可拆分的配送模式优于独立配送下单中心送取需求可拆分的配送模式。研究成果不仅拓展了车辆路径问题,还可为相关快递物流企业配送优化提供决策参考。     

Optimal switch location in mobile communication networks using hybrid genetic algorithms

The optimal positioning of switches in a mobile communication network is an important task, which can save costs and improve the performance of the network. In this paper we propose a model for establishing which are the best nodes of the network for allocating the available switches, and several hybrid genetic algorithms to solve the problem. The proposed model is based on the so-called capacitated p-median problem, which have been previously tackled in the literature. This problem can be split in two subproblems: the selection of the best set of switches, and a terminal assignment problem to evaluate each selection of switches. The hybrid genetic algorithms for solving the problem are formed by a conventional genetic algorithm, with a restricted search, and several local search heuristics. In this work we also develop novel heuristics for solving the terminal assignment problem in a fast and accurate way. Finally, we show that our novel approaches, hybridized with the genetic algorithm, outperform existing algorithms in the literature for the p-median problem.     

遗传算法与禁忌搜索算法的混合策略在VRPTM问题上的应用

该文探讨了如何将基于遗传算法和禁忌搜索算法的混合策略应用于求解有时间窗的车辆路径(VRPTM)问题,给出了相应的应用算法。实验结果表明,这种将禁忌搜索作为变异操作的混合策略对VRPTM问题是行之有效的,其优化性能优于简单的遗传算法。     

Locomotive assignment and freight train scheduling using genetic algorithms

This study considers the movement of freight trains through a passenger rail network, a common occurrence in many developing countries. Passenger trains run according to a fixed schedule while freight trains need to be accommodated and run on the same track, ensuring that they do not interfere with passenger train movements. Operationally, this requires the assignment of a locomotive to a freight rake and then creating a workable schedule. Accordingly, we propose to solve the problem in two phases. In the first phase, we assign locomotives with partial scheduling with the objectives of minimizing total deadheading time and total coupling delay. We use a genetic algorithm to find non‐dominant locomotive assignment solutions and propose a method for evaluating its performance. The solutions are then ranked using two approaches, based on the decision maker's preferences. In the second phase, we select a locomotive assignment solution based on the ranking and find the lower bound on the arrival time of freight trains at their destinations. We use a genetic algorithm again to schedule the freight trains in the passenger rail network, with prescribed locomotive assignment precedence constraints with the objective of minimizing total tardiness. Computational results confirm the efficacy of the proposed method.     

变路网情况下多库房应急物资调度模型及算法

考虑一类大规模自然灾害应急救援情景,基于实际应用条件和需要,建立了最优变路网情况下多库房应急物资调度模型。探讨了车辆所依托的路网结构可变和多库房对调度算法的双重影响,设计了一种求解问题的动态加速自适应遗传算法。作为结论的直接应用,给出的仿真算例验证了问题模型及其求解算法的合理性和有效性。     

有时间窗车辆路径问题的混合智能算法

有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化,并且及时交换信息,弥补了蚁群算法和遗传算法各自的不足,达到了优势互补的效果,增强了算法的寻优能力,避免了停滞现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。     

求解动态车辆调度问题的混合禁忌搜索算法

对带时间窗的动态车辆调度问题进行分析,引入虚拟点和时间轴概念,建立基于时间轴的动态车辆调度模型,并提出基于C-W节约法和禁忌搜索的混合禁忌搜索算法进行求解.算法中使用动态方法构造候选解和动态禁忌长度的选取策略来提高算法的收敛速度,最后通过测试实例验证了该混合算法解决动态车辆调度问题的有效性和可行性.     

多车场多车型装卸混合车辆路径问题研究

为满足电子商务客户多样化和个性化的需求,建立了多车场、多车型的装卸混合车辆调度模型,并使用混合遗传启发式算法求解．首先采用混合编码,使问题变得更简洁;利用个体数量控制选择策略,以保证群体的多样性;引入２-交换变异策略,并结合爬山算法,加强染色体的局部搜索能力．然后,对混合遗传算法求得的精英种群进行禁忌搜索,提高了搜索效率．最后,通过实例计算表明了上述模型和算法的有效性．     

Stochastic optimization model of locomotive assignment to freight trains

Consideration was given to the optimization model of assigning the locomotives to the freight trains. The model was formulated in terms of a dynamic problem of stochastic programming with probabilistic constraints. The state variables characterize positions of the locomotives and trains at each time instant. The variables defining the motion of locomotives and their assignment to trains at each time instant play the role of controls. The expectation of the total freight traffic is the criterial function of the problem. A two-stage hybrid algorithm to solve the problem was developed. It combines the coordinatewise search and a genetic algorithm. Results of the numerical experiment were given.