Multicriteria Stochastic Shortest Path Problem for Electric Vehicles

This paper formulates the reliable routing of electric vehicles in stochastic networks as a multicriteria shortest path problem with travel time and charging cost components. The reliability term is defined as the probability of finishing the trip without running out of charge. The arc travel times are represented as stochastic variables, and arc energy consumption is modeled as a linear function of arc length and arc travel time. The traveler aims to minimize the generalized cost, formulated as a linear function of travel time and charging cost, subject to a minimum reliability threshold, representing the level of risk a traveler is willing to take in favor of routes with lower cost. We propose a solution algorithm based on generalized dynamic programming and show that the optimal solution may include cycles that visit at least one charging station. The properties of the proposed multicriteria shortest path problem are mathematically proved. The simulation results on randomly-generated networks show that cyclic paths are very rare, and that the generalized cost of travel is a monotone increasing function of minimum reliability threshold.     

突发灾害下可靠路径搜索模型与算法

在分析突发灾害爆发时可靠路径搜索问题特点的基础上,提出了一种在不确定网络中不依赖于弧的旅行时间概率分布的可靠路径搜索方法。该方法通过场景集描述网络旅行时间的不确定性,应用Minimax理论构建求解所有场景下可靠路径的数学模型,并设计了问题求解算法,分析了算法的时间复杂性,最后通过典型算例对算法进行了验证。     

Smart robotic mobile fulfillment system with dynamic conflict-free strategies considering cyber-physical integration

Smart mobile robots are deployed to the warehouse environments to improve the efficiency, because of its characteristics of high automation and flexibility characteristics. However, the trajectory planning is a great challenge especially when a number of mobile robotics operates in the warehouse simultaneously. This paper proposes a cyber-physical system model for smart robotic warehouse to implement the workflow data collection and procedure monitor. A decoupled method is presented to find a conflict-free path for the mobile vehicles in the warehouses, after distributing destinations to mobile robots to minimize the total travel distance. The improved A* algorithm is applied to find paths from the source node to the destination node for single mobile vehicle in the domain of smart logistics. Collisions are detected by comparing the occupying time window of each mobile vehicle. Three collision avoidance strategies are developed to solve the conflicts and the candidate path with the minimal completion time is selected as the final determined route. The contribution of the paper is to propose a CPS-enabled robotic warehouse with dynamic conflict-free strategy to self-configure the path to optimize warehouse operation efficiency.     

Capacitated single-allocation hub location model for a flood relief distribution network

In disaster management, the logistics for disaster relief must deal with uncontrolled variables, including transportation difficulties, limited resources, and demand variations. In this work, an optimization model based on the capacitated single-allocation hub location problem is proposed to determine an optimal location of flood relief facilities with the advantage of economies of scale to transport commodities during a disaster. The objective is to minimize the total transportation cost, which depends on the flood severity. The travel time is bounded to ensure that survival packages will be delivered to victims in a reasonable time. Owing to complexity of the problem, a hybrid algorithm is developed based on a variable neighborhood search and tabu search (VNS-TS). The computational results show that the VNS found the optimal solutions within a 2% gap, while the proposed VNS-TS found the optimal solution with a 0% gap. A case study of severe flooding in Thailand is presented with consideration of related parameters such as water level, hub capacity, and discount factors. Sensitivity analyses on the number of flows, discount factors, capacity, and bound length are provided. The results indicated that demand variation has an impact on the transportation cost, number of hubs, and route patterns.     

模糊随机环境下考虑残次品处理的库存配送问题研究

针对考虑残次品的多生产商选择多商品多阶段库存配送问题,建立了一个基于动态规划的双层库存配送模型。高端物流服务集成商以整个供应链网络成本最小为目标制定采购决策;库存配送服务商以运营成本最小为目标,在集成商决策下制定库存和配送决策。设计了模糊随机环境下基于动态规划的双层全局-局部-邻域粒子群算法（Bi-DPGLNPSO）对模型进行求解。并通过算例验证模型和算法的有效性和合理性。通过参数测试和算法对比检验算法的优越性。     

基于改进蚁群算法的物流运输路径研究

为了在复杂的交通环境中能够快速求解出物流运输的最优路径,在传统蚁群算法基础之上提出了一种基于改进蚁群算法的物流运输路径优化模型。首先,通过在传统蚁群算法中加入基于运输时间、成本、道路平均通畅程度因子的约束条件,同时改进传统信息素的更新方式,对道路上的信息素浓度进行最大最小限制,从而改变路径选择转移概率。最后,利用改进蚁群算法与CSAACO算法、ACO算法进行仿真实验,在相同实验环境条件下测试3种算法在物流运输路径的距离缩短量和时间减少量,实验数据表明,改进蚁群算法在运输距离和运输时间方面明显低于CSAACO算法和ACO算法。改进蚁群算法拥有更强的全局寻优能力,算法收敛速度更快,所需时间更少,获得的最优路径更短,提高了整个物流行业的运输效率。     

多目标多周期应急物流模型及其遗传算法求解

为解决拆分-配送车辆路由问题,建立多目标多周期应急物流模型,以最小化供需差异、总配送时间及灾点间的不均衡度为目标,通过加权求和,得到综合的目标函数,并设计新的编码规则,将配送方案映射为基因序列,由赌盘轮转法生成可行的初始种群,将灾点聚类后,利用遗传算法进化寻优。数值实验结果验证了该模型及其算法的有效性。     

基于GIS的应急物资调运信息系统研究*

针对应急物流的特点和需求,本文提出了一种基于GIS的应急物资调运信息系统,并对系统的总体结构、工作流程和基本功能模块进行了分析。最后,系统仿真证明了该系统通过基于灾害风险系数和GIS的动态优化路径选择方法,较好地满足了应急物资调运的时效性需求。     

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

基于电子眼的应急物流运输路径自动规划研究

传统应急物流运输路径自动规划方法无法对灾区路况进行整体把握,导致规划的路径中出现道路损毁的情况,车辆无法到达,影响安全的同时,绕路延长运输时间。因此,设计一种基于电子眼的应急物流运输路径自动规划方法。首先确定电子眼的相关参数,设计其工作逻辑,完成传输图像视频的遍历检测,为路径规划提供参考,选择GIS系统中的栅格数据,作为路径规划的评估依据,最后建立应急物流路径规划模型,重点考虑的就是行车速度和时间,建立目标函数和约束函数,求解后得到应急物流运输路径自动规划的结果。通过算例仿真的实验结果,证明设计的规划方法得到的路径方案能够减少运输时间和信息量,验证了设计的路径自动规划方法具有一定的可靠性。     

Robotic path planning using evolutionary momentum-based exploration

In this article, we propose a new algorithm to solve the problem of robotic path planning in static environment where the source and destination are given. A grid-based map has been used to represent the robotic world. The basic algorithm is built on an evolutionary approach, where the path evolves along with generations with each generation adding to the maximum possible complexity of the path. Along with complexity we optimise the total path length as well as the minimum distance from the obstacle in the robotic path. It may be seen that the value of evolutionary parameter number of individuals as well as the maximum complexity is less at start and more at the later stages of the algorithm. We use a Gaussian increase in these values whose parameter may be adjusted to control the time and output. Seven genetic operators have been implemented that include selection, crossover, soft mutation, hard mutation, insert, delete and elite. The phenotype representation consists of the coordinate where the robot is supposed to make a turn. This happens by the traversal of the path using these points by the evolutionary algorithm. Momentum determines the speed of the algorithm in this traversal.     

Cooperation and profit allocation in two-echelon logistics joint distribution network optimization

Collaborative two-echelon logistics joint distribution network can be organized through a negotiation process via logistics service providers or participants existing in the logistics system, which can effectively reduce the crisscross transportation phenomenon and improve the efficiency of the urban freight transportation system. This study establishes a linear optimization model to minimize the total cost of two-echelon logistics joint distribution network. An improved ant colony optimization algorithm integrated with genetic algorithm is presented to serve customer clustering units and resolve the model formulation by assigning logistics facilities. A two-dimensional colony encoding method is adopted to generate the initial ant colonies. Improved ant colony optimization combines the merits of ant colony optimization algorithm and genetic algorithm with both global and local search capabilities. Finally, an improved Shapley value model based on cooperative game theory and a cooperative mechanism strategy are presented to obtain the optimal profit allocation scheme and sequential coalitions respectively in two-echelon logistics joint distribution network. An empirical study in Guiyang City, China, reveals that the improved ant colony optimization algorithm is superior to the other three methods in terms of the total cost. The improved Shapley value model and monotonic path selection strategy are applied to calculate the best sequential coalition selection strategy. The proposed cooperation and profit allocation approaches provide an effective paradigm for logistics companies to share benefit, achieve win–win situations through the horizontal cooperation, and improve the negotiation power for logistics network optimization.     

Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problem

Traditional route planners commonly focus on finding the shortest path between two points in terms of travel distance or time over road networks.However,in real cases,especially in the era of smart cities where many kinds of transportation-related data become easily available,recent years have witnessed an increasing demand of route planners that need to optimize for multiple criteria,e.g.,finding the route with the highest accumulated scenic score along(utility)while not exceeding the given travel time budget(cost).Such problem can be viewed as a variant of arc orienteering problem(AOP),which is well-known as an NP-hard problem.In this paper,targeting a more realistic AOP,we allow both scenic score(utility)and travel time(cost)values on each arc of the road network are time-dependent(2TD-AOP),and propose a memetic algorithm to solve it.To be more specific,within the given travel time budget,in the phase of initiation,for each population,we iteratively add suitable arcs with high scenic score and build a path from the origin to the destination via a complicate procedure consisting of search region narrowing,chromosome encoding and decoding.In the phase of the local search,each path is improved via chromosome selection,local-improvement-based mutation and crossover operations.Finally,we evaluate the proposed memetic algorithm in both synthetic and real-life datasets extensively,and the experimental results demonstrate that it outperforms the baselines.     

Minimum cost VRP with time-dependent speed data and congestion charge

A heuristic algorithm, called LANCOST, is introduced for vehicle routing and scheduling problems to minimize the total travel cost, where the total travel cost includes fuel cost, driver cost and congestion charge. The fuel cost required is influenced by the speed. The speed for a vehicle to travel along any road in the network varies according to the time of travel. The variation in speed is caused by congestion which is greatest during morning and evening rush hours. If a vehicle enters the congestion charge zone at any time, a fixed charge is applied. A benchmark dataset is designed to test the algorithm. The algorithm is also used to schedule a fleet of delivery vehicles operating in the London area.     

考虑道路扩建的区域物流网络设计优化模型

通过对区域物流网络中边、点上费用、容量、流量等的分析,结合实际问题中对道路扩建和物流设施容量设计决策的需要,构建基于物流时间需求的区域物流网络设计数学模型。模型以最小化物流网络构建成本、初期运营成本和物流时间需求惩罚成本为目标,基于网络中物流量的特征给出了约束条件,分析模型的特点开发了改进的拉格朗日松弛算法并予以求解。计算机软件对模型和算法的仿真给出了物流网络构建中各项成本之间的关系,验证了模型和算法的有效性和实用性。     

考虑交通拥堵规避的低碳时变车辆路径问题研究

针对时变路网条件下的低碳车辆路径问题,首先,分析车辆离散行驶速度与连续行驶时间之间的关系,依据“先进先出”准则设计基于时间段划分的路段行驶时间计算方法,引入考虑车辆速度、实时载重、行驶距离与道路坡度因素的碳排放计算函数;然后,在此基础上以所有车辆的碳排放量最小为目标构建低碳时变车辆路径问题数学模型;最后,引入交通拥堵指数,设计交通拥堵规避方法,并根据模型特点设计一种改进蚁群算法求解.实验结果表明,所提出方法能有效规避交通拥堵、缩短车辆行驶时间、减少车辆碳排放,促进物流配送与生态环境和谐发展.     

考虑失效路段恢复的动态应急资源车辆调度模型

重大灾害救援中,应急资源车辆调度时常因某些道路毁损（通行功能失效）而绕行,相对延长了调度时间。基于现实可行性和必要性,将抢修失效路段与资源调度联为二级递阶系统,并考虑车辆行驶时间的动态性,建立了数学模型,同步规划道路恢复和车辆路径,为有效提升救援效率提供了新的途径。设计了双层基于启发式算法的求解策略,作为模型的直接应用和说明,最后的算例验证了模型和算法的合理性和可行性。     

基于自适应蚁群算法的公交查询算法设计

公交查询系统的设计可以解决在庞大的公交网络中公交路线选择的问题。该文将利用蚁群算法设计公交查询系统的核心算法．即如何搜索出一条从起始站点到目的站点的最优路径。该文将公交网络按直达关系抽象成有向图,用蚂蚁在各个节点之间的行走代表公交线路的选择。针对基本蚁群算法收敛速度和早熟之间的矛盾,提出了自适应信息素更新的蚁群算法,并设计了迟滞更新信息素的方法．使得运算量大大减少。     

A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier’s total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier’s total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.     

地震灾害下应急物流系统绩效评价

针对地震灾害下应急物流系统(ELS)绩效评价的问题,以地震灾害下的应急物流系统为研究对象,首先建立了ELS运作模型,并对该运作模型进行了分析;然后构建了地震灾害下应急物流系统绩效评价指标体系,并在上述基础上建立了基于BP神经网络的评价模型;最后将该评价方法应用于实例,验证了该评价方法的科学性和实用性。