基于蚁群系统和2-opt方法求解同时送取货车辆路径VRPSPD问题

研究了一般意义下同时送取货的车辆路径VRPSPD问题,建立VRPSPD的整数规划模型.考虑到VRPSPD车辆不断变化的负载量,使得问题难以求解,设计了一种将蚁群系统(ACS)与2-opt方法相结合的启发式算法.通过在蚁群系统(ACS)中引入候选集合的策略,将启发因子设为目标函数值,同时利用2-opt算法的思想得到适用于VRPSPD的2-opt方法,使得设计的启发式算法对于求解VRPSPD是有效的.最后,实例运算的结果也证明了算法是一种较好的算法,能够得到满意的解.     

循环取货模式下的多车场协同运输问题研究

分析循环取货模式和协同运输问题的关联性,提出了供需节点分离下的多车场一体化协同运输路线优化问题,考虑运输价值和运输成本,引入节点-弧流量的概念,通过比较流量大小确定节点集合,构建了问题的多供应点、多需求点运输模型.考虑取货的单向性和送货的闭合性,构造了求解模型的两阶段算法,运用动态规划的递推解法确定取货最优路线,然后基于余弦定理的几何法求解出发点和返回点不相同的送货路径优化问题,最后通过算例分析,说明了模型的合理性和算法的有效性.     

多商品分批次取送货的模糊需求车辆路径问题

为解决连锁企业库存不平衡问题,本文研究了考虑多商品多批次取送货的模糊需求车辆路径问题。该问题综合考虑了多货混装、多次访问、供需未匹配、客户需求不唯一以及需求不确定等因素。本文以运营成本最小为目标,构建MCVRPSPDFD数学模型,模型利用可信测度理论应对决策环境中的不确定因素,通过改进的禁忌搜索算法进行求解。为适应模型需求和提升运算效率,算法设计了合理的初始种群形成过程及编码解码方式,并通过参数测试选取合适的参数。算例结果显示,本文成果能有效解决连锁企业库存不平衡问题,决策者偏好值的变动会对运营成本产生影响。     

冷链物流同时送取货车辆路径优化

针对冷链物流同时送取货车辆路径优化问题,分析冷链物流配送中的车辆固定成本、行驶成本、制冷成本和货损成本等成本构成,以总成本最小化为目标,将冷链物流配送的送货和取货业务综合到每一个客户节点,建立单个配送中心和多个客户节点的冷链物流配送车辆路径优化模型,并采用遗传算法进行求解,算例分析验证了所建模型和设计算法的适用性和可行性,结果表明优化后的同时送取货车辆配送方案能够降低配送成本,提高配送效率,研究结论对冷链物流配送决策具有重要的参考价值.     

基于模糊需求的多产品供应商选择的多目标规划模型

由决策于环境的不确定性,供应商选择问题存在大量的模糊信息,传统的确定性规划模型已经不能够很好地处理此类问题。本文基于模糊需求量信息,对于多产品供应商问题建立了模糊多目标规划模型。同时考虑到各目标及约束的重要性程度不同的影响,通过引进适当的权重对多目标规划模型进行求解。文中结合实际算例验证模型的可行性和有效性。     

具有模糊目标的多目标双矩阵对策集结与求解

针对不确定性多冲突环境,建立了多个具有模糊目标的多目标双矩阵对策的综合集结模型.在假定局中人各模糊目标的隶属函数为线性函数的情形下,基于总体模糊目标的可达度,给出了纳什均衡解的定义,并应用粒子群优化算法对集结模型求解.最后,给出一个军事例子说明了模型的实用有效性和粒子群优化算法求解的高效性.     

到货不确定的多商品多阶段多折扣的采购与存储问题

考虑一个制造商和多个供应商的采购与存储问题。多个供应商分别提供多种原材料，采用一种折扣方案，或单品全量折扣，或总量全量折扣，或混合全量折扣。制造商根据供应商提供的原材料品种和折扣方案，考虑不能按时到货的情况下，确定订货量，制定运输和仓储方案，以最小化总体运营成本。受运输过程中多种因素的影响，到货时间存在一定的不确定性，由此引出调货问题。用模糊随机变量表示到货率，建立相应的模糊随机数学优化模型，通过建立模糊随机期望值模型的方法将不确定的模糊随机优化模型转化为确定的混合整数非线性规划模型。给出求解该问题的算法——基于核搜索的启发式算法，对算例求解并证明了算法的可行性与有效性。通过数值实验，对相关参数进行分析，给出其经济解释，为管理者决策提供参考。     

两阶段模糊生产计划期望值模型

在现实的生产系统中,生产计划问题常常是-个确定的线性规划问题.但是,在许多的实际情况中,由于生产系统中不确定性因素的影响,带有常系数的线性规划模型不能合理地描述现实的决策环境.为了准确有效地描述生产决策环境,本文提出一类新的带有模糊参数的两阶段生产计划期望值模型并且讨论模型的一些基本性质.然后,讨论补偿函数的逼近并且设计-个基了:逼近方法、神经网络和遗传算法的启发式算法来求解这个两阶段模糊生产计划模型.最后,给出一个数值例子来表明所设计算法的可行性和有效性.     

基于可信性理论的均值-熵-偏度投资组合模型及其算法求解

本文考虑到证券市场的投资者往往面临着随机和模糊两种不确定性的情形,在模糊随机环境下把证券的收益率视作三角模糊变量,在可信性理论基础上建立了带融资约束条件的均值-熵-偏度三目标投资组合决策模型,拓展了基于可信性理论的投资组合决策模型的研究内容,同时通过对约束条件处理方法,外部档案维护方法等关键算子的改良,提出了一种新的约束多目标粒子群算法。本文运用该算法对模型进行求解,把得到的最优解与传统的多目标粒子群算法得到的最优解进行对比,结果表明新算法得到的最优解的质量会显著地优于传统的多目标粒子群算法的最优解,从而验证了算法的有效性和准确性。该算法可以在三维空间中得到一个分布性和逼近性较好的Pareto最优曲面,满足投资者对不同目标的差异需求,为投资者提供合理的投资组合决策方案。     

一个基于货物运输的批处理机随机调度模型研究

本文以货物运输为背景新建立了一个批处理机随机调度模型,目的是为了应付货物运输中运输时间的不确定性和货主取货时间的不确定性.首先将模型转化为与其等价的确定优化问题,接着研究给出了确定优化问题的性质,最后基于这些性质给出了一个求解确定优化问题的启发式算法.该问题的解决可望为物流公司等进一步改善服务质量提供了一些理论依据     

Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery

The vehicle routing problem (VRP) with simultaneous pickup and delivery (VRPSPD) is an extension of the classical capacitated VRP (CVRP). In this paper, we present the saving heuristic and the parallel saving heuristic for VRPSPD. Checking the feasibility of a route in VRPSPD is difficult because of the fluctuating load on the route. In the saving heuristic, a new route is created by merging the two existing routes. We use a cumulative net-pickup approach for checking the feasibility when two existing routes are merged. The numerical results show that the performance of the proposed heuristics is qualitatively better than the existing insertion-based heuristics.     

快递企业“最后一公里”快件收派优化方案研究

本文以快递公司快件收派服务为背景,对区域收派路线规划问题进行研究,结合A快递公司实际运作情况进行案例分析,综合考虑收派混合、动态性、时间窗和容量约束四个最主要的因素,建立数学模型,设计收派流程,通过改进的禁忌搜索算法在短时间内得到优化的路径结果,并在收派活动进行中动态处理新需求及实时更新收派路径,以提高收派效率。基于该企业实际数据的计算结果表明,本文提出的相应流程和算法比实际操作获得更好的解。     

Vehicle routing problem with simultaneous deliveries and pickups

The vehicle routing problem with backhauls involves the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the distribution centre and a pickup of recycled items simultaneously. In this paper, an insertion-based procedure to generate good initial solutions and a heuristic based on the record-to-record travel, tabu lists, and route improvement procedures are proposed to resolve the vehicle routing problems with simultaneous deliveries and pickups. Computational characteristics of the insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational results show that the insertion-based procedure obtained better solutions than those found in the literature. Computational experiments also show that the proposed hybrid heuristic is able to reduce the gap between initial solutions and optimal solutions effectively and is capable of obtaining optimal solutions very efficiently for small-sized problems.     

An algorithm for the traveling salesman problem with pickup and delivery customers

The paper extends the branch and bound algorithm of Little, Murty, Sweeney, and Karel to the traveling salesman problem with pickup and delivery customers, where each pickup customer is required to be visited before its associated delivery customer. The problems considered include single and multiple vehicle cases as well as infinite and finite capacity cases. Computational results are reported.     

A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery

This paper addresses a location-routing problem with simultaneous pickup and delivery (LRPSPD) which is a general case of the location-routing problem. The LRPSPD is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with same vehicle and the overall cost is minimized. We propose an effective branch-and-cut algorithm for solving the LRPSPD. The proposed algorithm implements several valid inequalities adapted from the literature for the problem and a local search based on simulated annealing algorithm to obtain upper bounds. Computational results, for a large number of instances derived from the literature, show that some instances with up to 88 customers and 8 potential depots can be solved in a reasonable computation time.     

基于即时配送和收益激励的众包物流运力调度研究

基于参与众包物流配送模式的人员闲散、积极性不高,以及客户对即时配送要求并非完全刚性的特征,引入模糊时间窗,将客户满意度量化为众包物流配送人员到达客户位置时刻的模糊隶属度函数。在一定客户满意度下,以最大化众包物流配送人员收益为目标,构建了基于即时配送和收益激励的众包物流运力调度问题模型,考虑到机会、逾时、超载惩罚成本,利用带有动态权重的粒子群算法,通过算例验证分析,结果表明该模型在保证客户满意度和提高众包物流配送人员积极性方面具有可行性和有效性。     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

A fuzzy-based decision support model for monitoring on-time delivery performance: A textile industry case study

This paper investigates uncertainties in complex supply chain situations and proposes a fuzzy-based decision support model for determining the chance of meeting on-time delivery in a complex supply chain environment. It integrates fuzzy logic principles and unitary structure-based supply chain model and enables addressing uncertainties associated with key inputs of on-time delivery performance for effective decision making process. The proposed pragmatic model deals with the fuzziness of the key inputs including, variations in demand forecasting, materials shortages and distribution lead time, and combines a fuzzy reasoning approach for monitoring on-time delivery of finished products. In systematically dealing with the uncertainties of complex supply chains, this model supports the minimizing of business losses that result from penalties and customer dissatisfaction, and the consequent reduced market share. Application of the proposed model is illustrated using a textile industry case study.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.