Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.

     

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

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

Scheduling with few changes

In this work we consider scheduling problems where a sequence of assignments from products to machines – or from tasks to operators, or from workers to resources – has to be determined, with the goal of minimizing the costs (=money, manpower, and/or time) that are incurred by the interplay between those assignments. To account for the different practical requirements (e.g. few changes between different products/tasks on the same machine/operator, few production disruptions, or few changes of the same worker between different resources), we employ different objective functions that are all based on elementary combinatorial properties of the schedule matrix. We propose simple and efficient algorithms to solve the corresponding optimization problems, and provide hardness results where such algorithms most likely do not exist.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

On the Hierarchical Chinese Postman Problem with linear ordered classes

The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn⁴) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity.     

Efficient offline algorithms for the bicriteria k-server problem and online applications

In this paper we consider the bicriteria version of the well-known k-server problem in which the cost incurred by an algorithm is evaluated simultaneously with respect to two different edge weightings.We show that it is possible to achieve the same competitive ratios of the previously known online algorithms with a dramatic improvement of the running time, i.e., from exponential to polynomial.Such results are obtained by exploiting new polynomial time algorithms able to find offline solutions whose costs differ from the optimal ones only of additive terms independent from the sequence of requests.     

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.     

Max-min matching problems with multiple assignments

In job assignment and matching problems, we may sometimes need to assign several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples include the assignment of courses to faculty, consultants to projects, etc. In terms of objectives, we may wish to maximize profits or minimize costs, or maximize the minimal value (max-min criterion) of an attribute such as the performance rating of a processor in the matching, or combine the two goals into one composite objective function entailing time-cost tradeoffs. The regular bipartite matching algorithms cannot solve the matching problem, when upper and lower bounds are imposed on the number of assignments. In this paper, we present a method, referred to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.     

ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

要素成本上升背景下我国外贸的中长期趋势分析

本文在近年来广义要素成本上涨的背景下,利用HS98章商品2010-2014年的月度数据,对我国出口商品的国际市场竞争力进行中长期动态预测。文中选取显示性比较优势指数(RCA)作为表征贸易商品竞争力的度量指标,结合要素成本上涨的背景,利用马尔可夫链动态模型,对我国外贸的中长期趋势进行预测。研究发现:短期内在广义要素成本上升的背景下,第一产业的大部分商品及第二产业中纺织原料及纺织品受到较大冲击;从长期趋势来看,第一产业维持了稳定的比较优势,而对于第二产业其影响效应分化,纺织原料及纺织品、轻工业产品、陶瓷及玻璃制品的国际竞争优势呈明显下跌趋势,而矿产品、普通和精密机械、木制品和纸制品的国际市场竞争力并无明显变化,第二产业受到的长期影响要比短期更显著。     

A hybrid metaheuristic approach to solving the UBQP problem

This paper presents a hybrid metaheuristic approach (HMA) for solving the unconstrained binary quadratic programming (UBQP) problem. By incorporating a tabu search procedure into the framework of evolutionary algorithms, the proposed approach exhibits several distinguishing features, including a diversification-based combination operator and a distance-and-quality based replacement criterion for pool updating. The proposed algorithm is able to easily obtain the best known solutions for 31 large random instances up to 7000 variables (which no previous algorithm has done) and find new best solutions for three of nine instances derived from the set-partitioning problem, demonstrating the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency. Furthermore, some key elements and properties of the HMA algorithm are also analyzed.     

Exploiting locality: approximating sorting buffers

The sorting buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.     

供给能力一定条件下的物流网络优化研究

第三方物流为了给客户提供正确且高效的服务,对物流进行了领域整合,建立了连接供应商和顾客的多级物流网络,网络包括了运输、流通加工、储存及配送等物流子系统。为降低网络系统成本,提高服务效率,针对网络中节点和通道上固定的物流供给能力,设计了以运营成本为目标的优化模型,通过变分不等式求出了最佳的物流组织方案,同时根据运行方案对网络中基础设施进行了重新设计改造,避免了资源不必要的浪费。最后通过算例对模型和算法进行了验证。     

基于灰色规划理论的综合物流服务中心优化研究

随着国民经济的进一步发展,物流作为承载经济交易枢纽的关键环节对经济发展起着重要的促进作用,综合物流中心作为物流行业统筹规划的重要组成部分对物流效率的提高具有深远的影响.当前综合物流中心主要存在结构不合理,市场导向性差等弊端.本文主要利用灰色规划理论结合物流收益值的获取、预测等过程对综合物流中心进行了优化研究.结果表明,...     

计及客户满意度的电动汽车物流配送路径规划与充放电管理

物流配送作为一种盈利型社会服务性行业,配送服务时间对客户满意度具有重要影响。论文考虑电动汽车(electric vehicle, EV)在配送途中和回到配送中心两个阶段,以物流配送成本最低和客户平均满意度最高为目标,构建了一种EV在换电模式下计及客户满意度的物流配送路径规划与充放电管理多目标优化模型,其中物流配送成本包括换电成本、车辆损耗成本以及慢速充放电成本。最后,以A-n29节点VRP基准测试系统插入四座换电站节点为例进行数值仿真,采用非支配排序遗传算法(Non-dominated sorting genetic algorithm, NSGA-II)对所提多目标优化模型进行求解,结果验证了所提方法的可行性和有效性。此外,论文进一步考查了EV慢速充放电管理对配电系统的影响,并对EV发车时间作了参数灵敏度分析,为管理者提供一些参考。     

中国物流业碳排放特征及其影响因素分析——基于LMDI分解技术

在对我国物流业碳排放特征进行分析的基础上,运用LMDI分解技术,建立中国物流业人均碳排放的因素分解模型,定量分析了1991-2010年能源结构、能源效率、运输方式、物流发展、经济增长以及人口等6种因素对物流业人均碳排放的影响.分析表明:经济增长是拉动物流业碳排放增长最主要的动力,在研究期间呈指数增长的趋势.运输方式对碳排放增长也表现出明显的促进作用,能源结构和能源效率虽然表现出拉动作用,但效果微弱.而物流发展因素则对物流业人均碳排放量表现出明显的抑制作用.因此,应大力推进物流业科技水平的提高,进一步发挥物流发展因素对碳排放的抑制作用,同时,优化物流运输体系,形成以铁路为主体,水运和管道为支撑,公路和航空运输为辅的低碳化的综合运输体系.     

An integrated approach for collection network design,capacity planning and vehicle routing in reverse logistics

This study considers network design, capacity planning and vehicle routing for collection systems in reverse logistics. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the return demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport returns at demand points to the opened collection points and travel the opened collection points by vehicles. Unlike the location-routing problems, the integrated problem considered in this study has several features: multi-period dynamic model, capacity planning for collection points, maximum allowable collection distances, etc. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested, and their test results are reported. In particular, the efficiency of the integrated approach is shown by comparing the two algorithm types.     

改进的生成树遗传算法及其在物流配送成本优化中的应用

针对物流配送成本优化问题的特点,建立了数学模型,并对基本的生成树遗传算法进行了改进,同时详细阐述了改进的生成树编码的遗传算法在物流配送成本优化问题中的运用等关键技术.最后根据此算法设计了一个物流配送优化系统,解决了一个物流配送成本优化问题,效果良好.此系统对于中小型物流公司设计最优物流策略和降低物流成本有着很大的应用前景.