An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

We study a selective and periodic inventory routing problem (SPIRP) and develop an Adaptive Large Neighborhood Search (ALNS) algorithm for its solution. The problem concerns a biodiesel production facility collecting used vegetable oil from sources, such as restaurants, catering companies and hotels that produce waste vegetable oil in considerable amounts. The facility reuses the collected waste oil as raw material to produce biodiesel. It has to meet certain raw material requirements either from daily collection, or from its inventory, or by purchasing virgin oil. SPIRP involves decisions about which of the present source nodes to include in the collection program, and which periodic (weekly) routing schedule to repeat over an infinite planning horizon. The objective is to minimize the total collection, inventory and purchasing costs while meeting the raw material requirements and operational constraints. A single-commodity flow-based mixed integer linear programming (MILP) model was proposed for this problem in an earlier study. The model was solved with 25 source nodes on a 7-day cyclic planning horizon. In order to tackle larger instances, we develop an ALNS algorithm that is based on a rich neighborhood structure with 11 distinct moves tailored to this problem. We demonstrate the performance of the ALNS, and compare it with the MILP model on test instances containing up to 100 source nodes.     

运筹学在整车物流智能调度决策支持系统中的研究与应用

本文基于整车物流智能调度决策支持系统的研发、实施与运维的成功应用,论述运筹学在智能化上的应用路径以及实践驱动的学术路径。该系统是国内较早在汽车物流企业实现落地的智能化调度系统,其所形成的思想理论与方法技术揭示了运筹学在智能化应用上的核心价值,以及实践驱动的学术价值,对解决“卡脖子”难题提供示范性思路。本文提出运筹学在智能化研发上“三环七步”的整体研发框架。首先,分析智能化需求的运筹学特征,详细介绍汽车整车物流的发展趋势、瓶颈及智能调度需求;其次,论述运筹学系统模型的作用与建模方法,分析汽车整车物流系统模型的决策要素、目标及约束,提出汽车整车物流智能调度的运筹学应用问题。然后,提出“模式装箱”的新装箱理论问题,明确问题的计算难解性、可解性及核心科学特征。进一步,建立汽车整车物流调度应用问题与科学问题的混合整数线性规划模型;提出求解汽车整车物流调度问题的分支定界算法,以及大规模问题求解的时空分解及滚动求解方法与技术;提出面向运筹应用的生产测试及压力测试方法,给出汽车整车物流调度的测试分析的流程与结果。此外,提出深度集成整车运输管理系统与仓库管理系统、优化算法引擎驱动的分布式、多视图、多系统融合的智能调度决策支持系统。最后,论述该系统在实施过程中的推广使用和运维情况,并对运筹学应用及实践驱动的科学研究进行总结与展望。     

The inventory models under conditional trade credit in a supply chain system

In several recent investigations dealing with the economic order quantity with permissible delay in payments, the following assumptions are made:     

Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care

This paper addresses a vehicle scheduling problem encountered in home health care logistics. It concerns the delivery of drugs and medical devices from the home care company’s pharmacy to patients’ homes, delivery of special drugs from a hospital to patients, pickup of bio samples and unused drugs and medical devices from patients. The problem can be considered as a special vehicle routing problem with simultaneous delivery and pickup and time windows, with four types of demands: delivery from depot to patient, delivery from a hospital to patient, pickup from a patient to depot and pickup from a patient to a medical lab. Each patient is visited by one vehicle and each vehicle visits each node at most once. Patients are associated with time windows and vehicles with capacity. Two mixed-integer programming models are proposed. We then propose a Genetic Algorithm (GA) and a Tabu Search (TS) method. The GA is based on a permutation chromosome, a split procedure and local search. The TS is based on route assignment attributes of patients, an augmented cost function, route re-optimization, and attribute-based aspiration levels. These approaches are tested on test instances derived from existing VRPTW benchmarks.     

Dynamic inventory and pricing policy in a capacitated stochastic inventory system with fixed ordering cost

We study a dynamic inventory and pricing optimization problem in a periodic review inventory system with setup cost and finite ordering capacity in each period. We show that the optimal inventory control is characterized by an (s,s^′,p) policy in four regions of the starting inventory level.     

A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.