生鲜农产品配送中带时窗的VRP模型与算法

针对生鲜农产品配送时效性强的特点,应用模糊隶属度函数表示的时间窗反映客户满意度,引入生鲜度损耗系数反映农产品价格随时间推移而下降的特性,在此基础上,考虑配送总成本和顾客满意度两个目标,建立了生鲜农产品配送路径多目标优化模型,设计了求解模型的智能算法,并用算例对模型及算法的有效性进行验证,同时对模型参数进行了敏感性分析。研究结果表明:所建立的模型及设计的算法是有效的,可以为生鲜农产品车辆配送路径优化决策提供理论依据和实践指导。     

考虑顾客优先级的多目标O2O外卖即时配送路径优化研究

基于O2O外卖平台的配送现状,引入外卖平台顾客优先级概念,从顾客满意度和配送成本两个角度出发,建立了考虑客户优先级、带时间窗、动态、多车场多目标取送货车辆的路径模型,采用加权法将多目标转化成单目标,并设计改进的迭代局部搜索算法对模型进行求解,最后通过调研获取某校园周边外卖实际数据构造测试算例,通过数值实验,验证了模型和算法的有效性。实验结果表明:当成本权重超过一定数值时,成本下降空间变小,但顾客满意度会持续降低。     

带时间窗的同时取送货车辆路径问题求解算法

为了整合物流配送过程的退货与送货服务,依据实际情况建立带时间窗的同时取送货车辆路径规划模型,设计一种基于K-means聚类处理的Q-Leaning自启发式蚁群算法解决此类问题。根据配送服务的特性,在基本的K-means算法上作相应的改进,同时提高蚁群算法的局部搜索能力,完成两算法的合理衔接。选用相关文献数据和标准算例进行实验,验证所提算法具有较好的性能,可以解决所描述的此类问题。     

大规模基站运维优化与车队规划研究

研究了考虑充电量决策的大规模基站断电运维的多车辆路径规划问题。目标是在运维能力有限的条件下最小化基站断电产生的损失和车辆运行成本的加权总和。分析了该问题区别于传统取送货问题的差异与难点,利用图论模型建立了动态多阶段车辆路径的混合整数规划模型,利用库存理论辅助基站充电量的决策并通过软时间窗口对车辆服务与路径规划进行约束,最后设计了基于局部最优插入和变邻域搜索的动态算法框架进行求解。基于中国铁塔公司真实数据生成的多个算例验证了该算法可以显著降低运维成本,并协助公司进行运维车队规模的规划。     

基于分支定价算法的多时间窗家庭医护人员调度问题研究

为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解，并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试，将所提出的算法与CPLEX对比，验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现，客户提供多个可接受服务的时间窗能有效降低调度成本。     

基于时间窗的家庭医疗护理人力资源分配

随着中国人口老龄化程度加深和医疗资源短缺,社会对家庭医疗护理的需求大大增加。针对家庭医疗护理人力资源分配问题,提出将计算复杂且不能应用于大规模算例的带时间窗多期多车辆路径规划问题分解为资源分配、护理计划和路径规划问题。在资源分配阶段,建立了一个层次优化模型以优先平衡服务人员的利用率并避免客户访问冲突,应用一个概率模型使在没有求解路径规划问题的情况下考虑时间窗约束。设计了一个遗传算法来求解大规模资源分配问题。研究的原创性是在资源分配阶段考虑时间窗约束和所提出的层次优化算法。实验结果验证了模型的有效性。     

基于时间窗和多仓温控的生鲜商品配送车辆路径优化问题

目的 针对当前生鲜商品配送效率低和成本高等问题,采用车仓温度可控的多仓车辆作为配送装备,并结合时间窗等约束,研究基于时间窗和多仓温控的生鲜商品配送车辆路径优化问题。方法 建立最小化物流运营成本和车辆使用数量的双目标模型,然后设计基于Clarke-Wright节约算法的非支配排序遗传算法（CW-NSGA-Ⅱ）求解该模型。利用CW节约算法生成初始配送路径,以提高初始解的质量,并设计精英迭代策略,以提高算法的寻优性能。结果 基于改进的Solomon算例,将文中所提算法与多目标粒子群算法、多目标蚁群算法、多目标遗传算法进行了对比,验证了CW-NSGA-Ⅱ算法的求解性能。结合实例,对多仓车辆使用数量、温控成本和运营成本等指标进行对比分析,结果表明,经优化后多仓车辆使用数量减少了35.7%,温控成本减少了39.2%,物流运营总成本减少了47.7%。结论 文中所提模型和算法能够有效优化配送路径,降低运营成本,为构建高效率、低成本的生鲜配送网络提供了理论支持和决策参考。     

考虑客户满意度的车辆路径优化研究

针对传统的车辆路径问题较少关注客户满意度的情况，以客户对服务时间和货物完好性的要求来衡量客户满意度，构建基于模糊时间窗的时间满意度函数和基于货损率的货物完好满意度函数，在此基础上以客户满意度最大和运输成本最小为目标建立优化模型，设计相应算例并利用LINGO17.0软件进行求解，与中小物流企业常用的扫描法进行对比验证模型的有效性。结果表明：利用LINGO17.0求得的优化结果与扫描法相比，虽然运输成本有一定增加，但相应的平均客户满意度提高了36.3%，建立的模型能较好地平衡客户满意度和运输成本，对于物流企业配送路径的决策优化有一定的参考价值。     

动态的可选择可重复取送货基站运维路径优化研究

为了解决动态的可选择可重复取送货车辆路径优化问题,建立了基于动态需求的VRP模型。对于实时到来的需求,将动态的问题分解成多个静态的问题来求解。每次求解时,用初始插入算法得到初始解,设计改进的变邻域搜索算法来改善初始解。为了准确计算车辆到达配送点的时间,从百度地图实时读取任意两点的交通时间。利用铁塔公司历史数据构造多个算例表明,所提算法在1 min内得到较优解,和公司现有经验相比平均提升了46.47%,与插入算法相比平均提升30.38%。目前该算法已应用在该公司实际的基站运维中,有效地降低了该公司运维成本。     

考虑拥堵情形的污染路径问题及其求解算法

考虑拥堵情形的污染路径问题是经典的带时间窗车辆调度问题的一个扩展。该问题的目标函数包括车辆行驶产生的排放成本,约束条件则包括交通拥堵带来的车辆行驶速度约束——该拥堵只与时间有关(time-dependent),且拥堵的开始时刻和结束时刻都可以自由设定。首先提出了拥堵情形下的行驶时间计算模型,在此基础上建立污染路径问题的线性规划模型,并提出了基于节点时间窗变换以及速度和出发时间优化的求解算法。算例结果验证了该算法的高效性。     

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

With the expansion of the application scope of social computing problems, many path problems in real life have evolved from pure path optimization problems to social computing problems that take into account various social attributes, cultures, and the emotional needs of customers. The actual soft time window vehicle routing problem, speeding up the response of customer needs, improving distribution efficiency, and reducing operating costs is the focus of current social computing problems. Therefore, designing fast and effective algorithms to solve this problem has certain theoretical and practical significance. In this paper, considering the time delay problem of customer demand, the compensation problem is given, and the mathematical model of vehicle path problem with soft time window is given. This paper proposes a hybrid tabu search (TS) & scatter search (SS) algorithm for vehicle routing problem with soft time windows (VRPSTW), which mainly embeds the TS dynamic tabu mechanism into the SS algorithm framework. TS uses the scattering of SS to avoid the dependence on the quality of the initial solution, and SS uses the climbing ability of TS improves the ability of optimizing, so that the quality of search for the optimal solution can be significantly improved. The hybrid algorithm is still based on the basic framework of SS. In particular, TS is mainly used for solution improvement and combination to generate new solutions. In the solution process, both the quality and the dispersion of the solution are considered. A simulation experiments verify the influence of the number of vehicles and maximum value of tabu length on solution, parameters’ control over the degree of convergence, and the influence of the number of diverse solutions on algorithm performance. Based on the determined parameters, simulation experiment is carried out in this paper to further prove the algorithm feasibility and effectiveness. The results of this paper provide further ideas for solving vehicle routing problems with time windows and improving the efficiency of vehicle routing problems and have strong applicability.     

A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows

This article puts forward a cloud theory-based particle swarm optimization (CTPSO) algorithm for solving a variant of the vehicle routing problem, namely a multiple decision maker vehicle routing problem with fuzzy random time windows (MDVRPFRTW). A new mathematical model is developed for the proposed problem in which fuzzy random theory is used to describe the time windows and bi-level programming is applied to describe the relationship between the multiple decision makers. To solve the problem, a cloud theory-based particle swarm optimization (CTPSO) is proposed. More specifically, this approach makes improvements in initialization, inertia weight and particle updates to overcome the shortcomings of the basic particle swarm optimization (PSO). Parameter tests and results analysis are presented to highlight the performance of the optimization method, and comparison of the algorithm with the basic PSO and the genetic algorithm demonstrates its efficiency.     

An integrated approach to the vehicle routing and container loading problems

Real-world distribution problems raise some practical considerations that usually are not considered in a realistic way in more theoretical studies. One of these considerations is related to the vehicle capacity, not only in terms of cubic meters or weight capacity but also in terms of the cargo physical arrangements. In a distribution scene, two combinatorial optimization problems, the vehicle routing problem with time windows and the container loading problem, are inherently related to each other. This work presents a framework to integrate these two problems using two different resolution methods. The first one treats the problem in a sequential approach, while the second uses a hierarchical approach. To test the quality and efficiency of the proposed approaches, some test problems were created based on the well-known Solomon, Bischoff and Ratcliff test problems. The results of the integrated approaches are presented and compared with results of the vehicle routing problem with time windows and the container loading problem applied separately.     

Indirect search for the vehicle routing problem with pickup and delivery and time windows

The vehicle routing problem with pickup and delivery and time windows (VRPPDTW) is one of the prominent members studied in the class of rich vehicle routing problems and it has become one of the challenges for developing heuristics which are accurate and fast at the same time. Indirect local search heuristics are ideally suited to flexibly handle complex constraints as those occurring in rich combinatorial optimization problems by separating the problem of securing feasibility of solutions from the objective-driven metaheuristic search process using simple encodings and appropriate decoders. In this paper we show that the approach of indirect local search with greedy decoding (GIST) is not only flexible and simple but when applied to the VRPPDTW it also gives results which are competitive with state-of-the-art VRPPDTW-methods by Li and Lim, as well as Pankratz.     

车载可补货无人配送小车配送路径研究

无人配送小车由于不适合长距离运输,可与货车搭配完成“最后一公里”配送任务以增加服务范围,这对车辆路径优化问题提出了新的挑战。针对配送小车数量有限、城市配送货物量大且货车停靠限制的特点,提出无人配送小车可补货的大车-小车路径优化问题,即一辆货车搭载多台无人配送小车,由无人配送小车给客户送货,无人配送小车可在货车处补充货物并执行多行程配送。构建以总配送距离最短为目标的整数规划模型,针对此模型设计混合遗传大邻域搜索算法,在遗传算法基础上增加大邻域搜索算法对个体优化。在算法优化过程中先优化小车路径,再在小车路径基础上优化大车路径。数值实验表明,对于小规模问题,所提算法最多花费CPLEX求解时间的6%便获得最优解;在改造的Solomon数据上,所提算法相对于遗传算法平均有95.5%的计算结果优势,相对于大邻域搜索算法平均有7.2%的计算结果优势,且数据量越大,优势越大。     

改进麻雀搜索算法求解多目标低碳冷链物流车辆路径问题

目的 在传统冷链物流的车辆路径问题模型基础上,考虑服务节点和车辆运输过程中产生的碳排放,并加入客户满意度,在有限资源情况下最小化路径成本和最大化客户满意度。方法 构建多目标低碳冷链物流车辆路径问题模型,将爬山算法局部搜索思想应用到麻雀搜索算法中,形成改进麻雀搜索算法,并用其对上海市某区域内的冷链物流配送路径优化问题算例进行求解。结果 通过与改进前及其他2种智能优化算法运行结果进行对比发现,改进后的麻雀搜索算法具有更快的寻优速度和更好的寻优能力,且改进后的算法对模型的碳排放效用性更高。结论 基于国家的低碳政策,设计出符合当下实情的低碳冷链物流运输模型,通过改进优化算法设计运输方案,验证了爬山算法局部搜索思想对麻雀搜索算法进行改进的有效性及所构建低碳冷链物流车辆路径模型的合理性。     

A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints

Summary In this paper we deal with the following special vehicle routing problem with time window constraints: Given a non-homogeneous fleet of vehicles and a fixed set of customers, during one time period, i.e. a day or a week, these customers have to be delivered in the first half of the period with a certain amount of goods. Thereby delivery may start at timet _start say at the depot and for every customer there is a so-called cut-off-time for the latest possible delivery. In addition to travel time there is a certain delivery-time associated with every customer. In the second half of the time period the vehicles have to pick-up certain amounts of goods and to ship them to the depot. Again there is a cut-off time for the earliest possible pick-up and a certain time-span consumed for every pick-up. We show how this problem can be formulated as a (highdimensional) set partitioning problem with two additional nontrivial sets of side-constraints. Assuming that the number of customers that can be served by a single vehicle on a delivery or pick-up-pass is at most two, the problem reduces to a matching problem with side-constraints. Although the problem is still NP-complete it becomes practicable in the sense that by relaxation and applying effective optimization techniques from non-smooth optimization and efficient matching software good approximate solutions are constructed in acceptable time.This work was partially supported by a grant from the Deutsche Forschungsgemeinschaft (DFG)     

多配送中心冷链运输路径优化

目的 在降低配送成本的同时,保证生鲜配送的顾客满意度。方法 综合考虑运输距离、配送时间窗约束、生鲜变质等因素,以运输成本、制冷成本、车辆调用成本、配送中心开放和闲置成本及自提点对配送时间和生鲜品质的满意度为目标函数,建立双目标生鲜配送路径优化模型。结果 利用非支配排序遗传算法求得了不同需求情况下的生鲜配送方案。结论 在不同的需求状况下,合理选择开放配送中心能够在保证一定顾客满意度的情况下,有效降低了配送成本。     

带时间窗的汽车总装线物料配送路径规划

分析了现阶段汽车总装线物料配送中存在的问题,建立了适用于汽车总装线物料配送路径规划的混合时间窗模型,提出了解决带时间窗的汽车总装线物料配送路径优化问题的改进遗传算法,使用了一种新的染色体编码方式和与之对应的交叉算子。针对传统轮盘赌随机操作选择误差比较大的弊端,提出改进的轮盘赌选择算子,加大随机数的产生次数并加入排序选择的思想,融合了最佳个体保存选择策略,提高算子的选优性能。实验表明该算法用于求解带时间窗的汽车总装线物料配送路径问题的有效性。