Multi-depot vehicle routing problem with time windows under shared depot resources

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.     

Single-machine batch delivery scheduling with an assignable common due window

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O(n⁸)$O(n^8)$ time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.     

Vehicle routing using fixed delivery areas

In this paper we consider the problem of vehicle routing using fixed delivery areas. This is the problem of splitting the area serviced by a depot into a number of separate subareas—a single delivery vehicle being assigned to each subarea to supply all the customers within the subarea. A heuristic algorithm is developed for the problem based upon an initial allocation of customers to subareas followed by customer interchanges in an attempt to improve the subareas. Computational results are presented for a number of test problems drawn from the literature.     

Economic Production Lot Sizing with Periodic Costs and Overtime*

Traditional approaches for modeling economic production lot‐sizing problems assume that a single, fixed equipment setup cost is incurred each time a product is run, regardless of the quantity manufactured. This permits multiple days of production from one production setup. In this paper, we extend the model to consider additional fixed charges, such as cleanup or inspection costs, that are associated with each time period's production. This manufacturing cost structure is common in the food, chemical, and pharmaceutical industries, where process equipment must be sanitized between item changeovers and at the end of each day's production. We propose two mathematical problem formulations and optimization algorithms. The models' unique features include regular time production constraints, a fixed charge for each time period's production, and the availability of overtime production capacity. Experimental results indicate the conditions under which our algorithms' performance is superior to traditional approaches. We also test the procedures on a set of lot‐sizing problems facing a national food processor and document their potential economic benefit.     

Allocating a fixed cost based on data envelopment analysis and satisfaction degree

This paper uses the Data Envelopment Analysis (DEA) technique to solve the problem of allocating a fixed cost across a set of comparable decision making units (DMUs) in a fair way. It first investigates the effect of the fixed cost on each DMU and on the collection of DMUs. Next we prove that there exist some cost allocations which can make each DMU and the collection of DMUs efficient. We show that such a cost allocation is unique and equivalent to the proportional sharing method if the fixed cost allocation problem is a one-dimensional case. In a multidimensional case, the fixed cost allocations may not be unique. This paper defines the concept of satisfaction degree, and proposes a maxmin model and a corresponding algorithm to generate a unique fixed cost allocation. Finally, the proposed approach has been applied to a data set from prior literature.     

Reducing project duration at minimum cost: A time-cost tradeoff algorithm

The problem of reducing project duration efficiently arises frequently, routinely, and repetitively in government and industry. Siemens [1] has presented an inherently simple time-cost tradeoff algorithm (SAM—for Siemens Approximation Method) for determining which activities in a project network must be shortened to meet an externally imposed (scheduled) completion date (which occurs prior to the current expected completion date). In that paper the network activities of the example problem all have constant cost-slopes. Siemens mentions that the algorithm can be used where the activities have (convex) nonlinear cost-slopes—instead of just one cost-slope and one supply (time available for shortening) for each activity, there can be multiple cost-slope/supply pairs for each activity. This technique is illustrated in this paper. Also illustrated here is an improvement suggested by Goyal [2]. In step 12 of the original algorithm Siemens suggests a review of the solution obtained by the first eleven steps to eliminate any unnecessary shortening. Goyal's modification does this systematically during application of the algorithm by de-shortening (partially or totally) selected activities which were shortened in a prior iteration. He claims that, empirically at least, the technique always yields an optimal solution. Our experience verifies this claim (given the assumption of convex cost functions). The authors have modified the original algorithm so that the requirement for convex cost functions can now be relaxed. Unfortunately, this modification is made only at the expense of simplicity. To further complicate matters we found that Goyal's technique does not always yield an optimal solution when concave functions are involved and thus still another modification was required. These are discussed in detail below. Finally, we discuss the applicability of the algorithm to situations involving discrete time-cost functions.     

Assortment Planning for Vertically Differentiated Products

We consider the problem of a retailer managing a category of vertically differentiated products. The retailer has to pay a fixed cost for each product included in the assortment and a variable cost per product sold. Quality levels, fixed, and variable costs are exogenously determined. Customers differ in their valuation of quality and choose the product (if any) that maximizes their utility. First, we consider a setting in which the selling prices are also fixed. We find that the optimal set of products to offer depends on the distribution of customer valuations and might include dominated products, that is, products which are less attractive than at least one other product, on every possible dimension. We develop an efficient algorithm to identify an optimal assortment. Second, we consider a setting in which the retailer also determines the selling prices. We show that in this case the optimal assortment does not include any dominated product and does not vary with the distribution of customer valuations when there is no fixed cost. We develop several efficient algorithms to identify an optimal assortment and optimally price the products. We also test the applicability of our methods with realistic data for two product categories.     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. 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. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

蓄冷式多温集配路径优化模型

现实中,由于配送中心选址对占地面积、土地成本等要求较高,加之物流企业资金有限或交通拥堵等限制,配送中心的设置通常会远离市中心。为了减少集货与配送车辆往返配送中心的次数以及车辆行驶距离,本文以总成本最小化,包括车辆派遣成本、行驶成本、碳排放成本、违背时间窗的惩罚成本、保温柜/箱成本、非整箱货物的配送成本,构建了1个配送中心由大型车辆为m个供应商采用蓄冷柜/蓄冷箱集货,由1个虚拟接驳点(中型车辆)结合小型车辆为n个零售门店采用蓄冷箱多温共配的路径优化模型,并设计了基于蚁群算法的混合更新信息素策略。以20个零售门店与6个海鲜供应商的三种品温海鲜品为仿真算例,验证了模型的有效性。实例分析发现：引入虚拟接驳点的配送线路数低于单纯的配送线路数;时间窗限制越宽松,引入虚拟接驳点的优越性越突出;具有虚拟接驳点的多温集配总成本低于自配送中心的集配总成本;具有虚拟接驳点的蓄冷式多温集配尤其利于低碳环保的冷链系统构建。     

A memetic algorithm for the patient transportation problem

This paper addresses a real-life public patient transportation problem derived from the Hong Kong Hospital Authority (HKHA), which provides ambulance transportation services for disabled and elderly patients from one location to another. We model the problem as a multi-trip dial-a-ride problem (MTDARP), which requires designing several routes for each ambulance. A route is a sequence of locations, starting and terminating at the depot (hospital), according to which the ambulance picks up clients at the origins and delivers them to the destinations. A route is feasible only if it satisfies a series of side constraints, such as the pair and precedence constraints, capacity limit, ride time, route duration limit and time windows. Owing to the route duration limit, in particular, every ambulance is scheduled to operate several routes during the working period. To prevent the spread of disease, the interior of the ambulances needs to be disinfected at the depot between two consecutive trips. The primary aim of the problem investigated herein is to service more requests with the given resources, and to minimize the total travel cost for the same number of requests. In this paper, we provide a mathematical formulation for the problem and develop a memetic algorithm with a customized recombination operator. Moreover, the segment-based evaluation method is adapted to examine the moves quickly. The performance of the proposed algorithm is assessed using the real-world data from 2009 and compared with results obtained by solving the mathematical model. In addition, the proposed algorithm is adapted to solve the classic DARP instances, and found to perform well on medium-scale instances.     

Optimal Inventory Control with Dual‐Sourcing,Heterogeneous Ordering Costs and Order Size Constraints

We consider a dual‐sourcing inventory system, where procuring from one supplier involves a high variable cost but negligible fixed cost whereas procuring from the other supplier involves a low variable cost but high fixed cost, as well as an order size constraint. We show that the problem can be reduced to an equivalent single‐sourcing problem. However, the corresponding ordering cost is neither concave nor convex. Using the notion of quasi‐convexity, we partially characterize the structure of the optimal policy and show that it can be specified by multiple thresholds which determine when to order from each supplier and how much. In contrast to previous research, which does not consider order size constraints, we show that it is optimal to simultaneously source from both suppliers when the beginning inventory level is sufficiently low. We also show that the decision to source from the low‐cost supplier is not monotonic in the inventory level. Our results require that the variable costs satisfy a certain condition which guarantees quasi‐convexity. However, extensive numerical results suggest that our policy is almost always optimal when the condition is not satisfied. We also show how the results can be extended to systems with multiple capacitated suppliers.     

Estimation of distribution algorithms using Gaussian Bayesian networks to solve industrial optimization problems constrained by environment variables

Many real-world optimization problems involve two different subsets of variables: decision variables, and those variables which are not present in the cost function but constrain the solutions, and thus, must be considered during optimization. Thus, dependencies between and within both subsets of variables must be considered. In this paper, an estimation of distribution algorithm (EDA) is implemented to solve this type of complex optimization problems. A Gaussian Bayesian network is used to build an abstraction model of the search space in each iteration to identify patterns among the variables. As the algorithm is initialized from data, we introduce a new hyper-parameter to control the influence of the initial data in the decisions made during the EDA execution. The results show that our algorithm improves the cost function more than the expert knowledge does.

     

无统计信息假设下的多阶段报童决策

在不对需求做任何统计假设的情形下,该文用理论计算科学兴起的集成专家意见的弱集成算法研究多阶段报童决策。弱集成算法是一种指数加权平均集成方法,在一定的初始权重下,根据损失函数在线调整专家意见的权重。基于收益损失函数和固定订购量的专家意见,得到了与从累积收益角度研究相一致的决策方法;并扩展研究了带有回收价值的情形。理论上证明了决策方法的累积收益损失几乎不超过最优专家意见的累积收益损失。通过数值算例验证了决策方法的可行性和合理性,探讨了卖出价和成本价等因素对竞争性能的影响,说明了回收价值的引入大大提高了决策方法的竞争性能,具有重要的现实意义。     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题

取送货车辆路径问题在多点调拨系统普遍存在,属于NP-hard问题。该问题研究通常需考虑车场数、车型种类、货品种类、客户服务次数等诸多因素,已有文献多假设客户间供需已匹配、单车场、单车型、单货品和取送货需求一次性满足,优化目标多设置为总路径最短。而从企业运营实践来看,运输方案不仅要规划客户间访问路径,还需进行客户间供需匹配;运输成本不仅与运距有关,还涉及运输货品的重量和派车成本;运输网络中多车场、多车型和多货品更加常见,且客户需求量往往大于车辆装载能力。因此,本文首次尝试基于"运距×运量"的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标,建立同时考虑多车场、多车型、多货品、客户间供需未匹配和需求可拆分的取送货车辆路径问题模型,并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解,并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：1）本文提出的算法在求解质量和求解效率方面均优于相关文献中的算法;2）相对人工调拨方案,本文设计的方案能够帮助企业节约33%的运输成本和21%的车次。本研究不仅可拓展取送货车辆路径问题现有理论,而且可为企业实际运营提供决策支持。     

面向新零售的生鲜连锁企业城市配送网络优化研究

城市配送网络优化是生鲜连锁经营企业实施新零售的关键环节,本文研究新零售背景下生鲜企业城市配送网络面临的多业态门店选址及末端需求点分配问题。本文系统考虑多业态零售门店选址布局及覆盖范围、冷链设施配置、冷藏品类选择等生鲜新零售特征构建非线性混合整数规划模型,并设计混合拉格朗日松弛算法求解模型,通过与CPLEX对比验证本文算法的有效性。根据典型生鲜连锁企业重庆果琳的实际数据,运用本文模型及算法得到重庆果琳多业态零售门店布局、门店线上订单覆盖范围、门店冷藏最优品类和门店冷链设施配置方案,并探讨需求规模变动、消费者自提意愿、线上订单规模和气温变化等因素对城市配送系统的影响。结果发现相比重庆果琳现有配送网络,优化方案平均成本降低2.52%;生鲜连锁企业损耗成本占总成本超过70%,配置冷链设施总成本仅降低0.32%;需求规模变动对城市配送网络及单位配送成本的影响较小;消费者自提意愿、线上订单规模和气温变化不影响城市配送网络结构且对总成本影响较小。     

Approximation algorithms on 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is a natural generalization of the standard 0–1 linear knapsack problem (KP). In KPC, the capacity of the knapsack is not fixed, but can be adjusted by a continuous variable. This paper studies the approximation algorithm on KPC. Firstly, assuming that the weight of each item is at most the original capacity of the knapsack, we give a 2-approximation algorithm on KPC by generalizing the 2-approximation algorithm on KP. Then, without the above assumption, we give another 2-approximation algorithm on KPC for general cases by extending the first algorithm.     

Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning

We study an optimization problem of packing unequal spheres into a three-dimensional (3D) bounded region in connection with radiosurgical treatment planning. Given an input (R, V, S, L), where R is a 3D bounded region, V a positive integer, S a multiset of spheres, and L a location constraint on spheres, we want to find a packing of R using the minimum number of spheres in S such that the covered volume is at least V; the location constraint L is satisfied; and the number of points on the boundary of R that are touched by spheres is maximized. Such a packing arrangement corresponds to an optimal radiosurgical treatment planning. Finding an optimal solution to the problem, however, is computationally intractable. In particular, we show that this optimization problem and several related problems are NP-hard. Hence, some form of approximations is needed. One approach is to consider a simplified problem under the assumption that spheres of arbitrary (integral) diameters are available with unlimited supply, and there are no location constraints. This approach has met with certain success in medical applications using a dynamic programming algorithm (Bourland and Wu, 1996; Wu, 1996). We propose in this paper an improvement to the algorithm that can greatly reduce its computation cost.     

The effects of seasonal demand on depot location

Many of the cost functions associated with depot location algorithms assume an overall demand for a fixed period, usually one year. This paper describes an investigation into the effect of high seasonality within such demand figures on the optimal location of storage facilities. The preliminary results indicate that a more flexible approach for certain products could be worthwhile.