一类带时间窗车辆分配问题的贪婪算法

本文对一类带时间窗的车辆分配问题进行了分析,引入了车辆任务的概念,并将问题转化为车辆与车辆任务的匹配问题,同时制订了运输任务选择和车辆选择的贪婪策略,并在此基础上设计了车辆分配问题的贪婪算法,最后通过实例验证了算法的有效性。     

带退货和软时间窗的多仓库选址-路径问题研究

选址-路径问题(location routing problems, LRP)是集成物流网络研究中的难题,也是任何一个大型物流配送企业必须面对的管理决策问题。本文在仓库容量约束和车辆容量约束的基础上,结合送取货一体化的配送模式和客户服务时间要求,建立了带退货和软时间窗的多仓库选址-路径(MDLRP)数学模型。针对MDLRP问题求解的复杂性,引入局部搜索算法和重组策略,设计了自适应混合遗传算法,对模型进行整体求解。最后进行数值实验,表明本文提出的模型和改进算法具有实用性和优越性,可为选址和车辆运输决策提供重要参考依据。     

部分联合运输策略下的物流车辆路径优化问题研究

论文分析了物流车辆路径优化问题的特点,提出了企业自营物流和第三方物流协同运输的部分联合运输策略。根据客户需求节点的特点进行了节点分类,建立了以车辆调用成本、车辆运输成本、第三方物流运输成本之和最小为目标的整数线性规划模型。根据部分联合运输策略下各类客户需求点运输方式特点,构造了一种新的变维数矩阵编码结构,并对传统算法中概率选择操作方式进行修改,提出了一种新的智能优化算法并与枚举法和遗传算法的运算结果进行了算法性能对比分析。结果显示,本文提出的逆选择操作蚁群算法具有较快的运算速度和较高的稳定性,是求解此类问题的一种有效算法。     

路径既定条件下有害物品运输策略选择研究

对有害物品运输问题的研究,大多集中在考虑路径风险情形下的路径选择问题方面,对路径既定条件下运输策略的选择问题尚未涉及.利用概率分析方法,比较了路径既定条件下一定量有害物品选择一次运输策略和选择多次运输策略在发生事故的可能性、路径风险两方面的差异.结果发现,一次运输情形下,发生事故的可能性较小,路径风险也较小,要使可能损失赔偿与运输成本之和最小,决策者应尽可能选择大载重量运输车辆进行有害物品运输.     

基于特殊路径的局内车辆路径问题混合策略研究

针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析。     

带模糊时间窗的配送问题多目标优化研究

针对配送多目标优化问题,综合考虑车辆使用数、运输总里程和客户服务水平,基于双层规划的思想,解决了车辆数函数和运输里程函数的区间伸缩指标问题,并引入客户不满意度的模糊隶属度函数来描述配送服务水平。通过去量纲将三个优化目标转化为总目标函数的功效函数,并运用模糊层次分析法对三个函数分配权重,建立以车辆使用数最少、运输总里程最小、客户不满意度最低的标量化多目标模型,并运用模拟退火算法验证了模型的合理性和普适性。     

多车场多车型车辆调度问题及其遗传算法

研究多车场多车型车辆调度问题,建立了一种基于最小配送费用的数学模型,模型的配送费用在考虑基本运输费的基础上又引入了司机的工资支出,包括基本工资和加班费.在多车场多车型车辆调度模型中,一辆车可以为多个客户服务,但一个客户只能由一辆车提供服务.根据模型的这些特点,提出了一种新的染色体混合编码方案和遗传操作策略,从而借助遗传算法成功实现了模型的求解.数值仿真结果验证了算法的可行性.     

基于遗传算法的成品油二次配送车辆路径问题研究

研究了加油站需求已知前提下带时间窗的具有满隔舱运输约束的多车型成品油二次配送车辆路径问题.首先以总费用极小化为目标建立了具有满载运输约束的多车型成品油二次配送车辆路径问题的混合整数规划模型,其中总费用包括动用车辆的固定费用、车辆的运输费用、以及不满足时间窗约束的等待成本和惩罚成本等.然后基于成品油二次配送车辆路径问题的特点设计了求解模型的遗传算法,通过对车辆和加油站分别采用自然数编码方式、解码时考虑约束条件等策略有效避免了不可行解的产生.最后利用一个实际案例进行了模拟计算,结果显示根据方法得到的配送方案明显优于实际中凭经验得到的配送方案,总配送成本大约降低了9%.模型和算法为制订成品油二次配送方案提供了决策依据.     

危险化学品车辆路径问题的一个新模型及算法研究

危险化学品因其固有的危险性,容易引发事故,且事故后果往往很严重,对于危险化学品各个管理环节必须考虑其安全性.文章针对危险化学品运输环节的车辆路径选择问题,建立了同时考虑运输费用和运输安全风险的双目标优化模型.不同于该类传统模型,文章新引入了描述需求点访问次序的决策变量,减少了传统模型的决策变量个数和约束条件的数量,对传统模型进行了简化.针对新模型的求解,文章提出了一种改进的粒子群算法,将非支配解方法与种群杂交策略相结合来处理双目标问题,在迭代过程中加入了局部搜索策略以增强算法效率.数值实验说明改进的粒子群算法与传统的粒子群算法相比具有更优的搜索效率,能更有效地求解新模型.     

突发事件应急医疗物资调度的随机算法

传统的车辆路径问题(VRP)是为车辆设计将物资从仓库运送到各个需求客户的路线,使得总的运输费用(或时间)最小。在本文中,我们更关心的是使得未满足的需求量和总的物资延误时间最小。这个模型的一个非常重要的应用就是当大规模突发事件发生以后如何有效的将应急医疗物资运送到各个医疗单位,例如自然灾难,恐怖袭击之后,各个医院的医疗物资有限,需要从应急中心调集所需物资,在这种情况下,从应急中心分发应急物资过程中的运输费用就不再是最主要的考查因素,而更重要的是考虑物资到达医院的时间以及到达量,因为这两个因素直接与病人生命息息相关。本文的主要工作是改进了已有的局部搜索算法,通过引入随机算法的思想设计了求解模型的改进随机算法,可以得到模型更优的解,并通过计算机模拟案例说明了算法是行之有效的。     

A fuzzy goal programming and meta heuristic algorithms for solving integrated production: distribution planning problem

Integrated production–distribution planning is one of the most important issues in supply chain management (SCM). We consider a supply chain (SC) network to consist of a manufacturer, with multiple plants, products, distribution centers (DCs), retailers and customers. A multi-objective linear programming problem for integrating production–distribution, which considers various simultaneously conflicting objectives, is developed. The decision maker’s imprecise aspiration levels of goals are incorporated into the model using a fuzzy goal programming approach. Due to complexity of the considered problem we propose three meta-heuristics to tackle the problem. A simple genetic algorithm and a particle swarm optimization (PSO) algorithm with a new fitness function, and an improved hybrid genetic algorithm are developed. In order to show the efficiency of the proposed methods, two classes of problems are considered and their instances are solved using all methods. The obtained results show that the improved hybrid genetic algorithm gives us the best solutions in a reasonable computational time.     

Retrial queue with discipline of adaptive permanent pooling

A novel customer service discipline for a single-server retrial queue is proposed and analysed. Arriving customers are accumulated in a pool of finite capacity. Customers arriving when the pool is full go into orbit and attempt to access the service later. It is assumed that customers access the service as a group. The size of the group is defined by the number of customers in the pool at the instant the service commences. All customers within a group finish receiving the service simultaneously. If the pool is full at the point the service finishes, a new service begins immediately and all customers from the pool begin to be served. Otherwise, the customer admission period starts. The duration of this period is random and depends on the number of customers in the pool when the admission period begins. However, if the pool becomes full before the admission period expires, this period is terminated and a new service begins. The system behaviour is described by a multi-dimensional Markov chain. The generator and the condition of ergodicity of this Markov chain are derived, and an algorithm for computing the stationary probability distribution of the states of the Markov chain is given. Formulas for computing various performance measures of the system are presented, and the results of numerical experiments show that these measures essentially depend on the capacity of the pool and the distribution of the duration of the admission period. The advantages of the proposed customer service discipline over the classical discipline and the discipline in which customers cannot enter the pool during the service period are illustrated numerically.     

交货期可以指派的供应链排序问题

考虑了由一个制造商和多个客户组成的供应链系统.每个客户有多个订单交给制造商加工,且每个客户有一个可以接受的完工订单到达时间.制造商可以与客户进行协商来选定合适的交货期.完工的订单是采用直接运输方式分批配送的,每一批配送需要花费一定的时间和费用.目标是对每个订单指派合适的交货期,并且进行生产和配送的排序,以极小化总的交货期指派费用,订单误工费用与配送费用的和.考虑了多种情况,分别给出了相应的算法.     

Optimizing two-level reverse distribution networks with hybrid memetic algorithms

In a Two-Level Reverse Distribution Network, products are returned from customers to manufacturers through collection and refurbishing sites. The costs of the reverse chain often overtake the costs of the forward chain by many times. With some known algorithms for the problem as reference, we propose a hybrid memetic algorithm that uses linear programming and a heuristic for defining routes. Moreover, we describe heuristics for deciding locations, algorithms to define routes for the products, and problem-specific genetic operators. Memetic algorithms have returned the best results for all instances.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

智能制造环境下的备件生产与运输协同调度问题研究

智能制造和即时配送环境下的备件生产与运输协同调度问题是目前国内研究的一大热点,这是因为备件供应链响应速度已成为当前备件制造企业赢得客户的关键因素。为了提高客户满意度,尽可能缩短从客户下达定制化生产订单到订单配送完成的时间,本文建立了以所有客户总等待时间最短为目标的混合整数规划模型和集合覆盖模型,推导了最优解性质,并设计改进的分支定价算法求得最优解。通过将小规模算例结果与CPLEX进行对比,验证了模型和算法的有效性。多组算例测试结果表明,所提出的模型和算法可以有效提升智能制造环境下的备件供应链运作效率。     

包含随机客户的选择性旅行商问题建模及求解

针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润。同时考虑以上两种因素,建立该问题的数学模型, 目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大。其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径。随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解。最后通过多个计算比对结果表明,该算法具有较高的计算效率。     

Robust vehicle routing problem with deadlines and travel time/demand uncertainty

In this article, we investigate the vehicle routing problem with deadlines, whose goal is to satisfy the requirements of a given number of customers with minimum travel distances while respecting both of the deadlines of the customers and vehicle capacity. It is assumed that the travel time between any two customers and the demands of the customer are uncertain. Two types of uncertainty sets with adjustable parameters are considered for the possible realizations of travel time and demand. The robustness of a solution against the uncertain data can be achieved by making the solution feasible for any travel time and demand defined in the uncertainty sets. We propose a Dantzig-Wolfe decomposition approach, which enables the uncertainty of the data to be encapsulated in the column generation subproblem. A dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. The results of computational experiments involving two well-known test problems show that the robustness of the solution can be greatly improved.     

Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points

The problem of scheduling delivery vehicles from a number of depots to customers, subject to constraints on load and distance or time, is considered. A new algorithm is presented; this allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots. Where too many customers require service, a flexible priority rule will select those to be served. Results for the single depot case are compared with other known algorithms; further results are given and discussed for cases of several depots.