“仓店一体化”模式下订单拣选与配送集成调度优化

针对“仓店一体化”模式下提供限时送达服务的新零售仓店,研究多拣货员、多客户、配送方式为带限时送达约束的路径优化分批配送情形下的订单拣选与配送集成调度问题。以最小化订单最大履行时间和配送成本为目标,构建了混合整数非线性规划模型,并设计两阶段启发式算法(H-2)进行求解,最后通过数值实验对算法进行验证与分析。数值实验结果表明,H-2具有较高的求解质量;相较于传统调度算法(TS)在效率提升、资源节约以及客户满意度提高方面具有更优的表现,进而为新零售仓店管理者提供决策支持。     

Centered -discrepancy of random sampling and Latin hypercube design, and construction of uniform designs

In this paper properties and construction of designs under a centered version of the -discrepancy are analyzed. The theoretic expectation and variance of this discrepancy are derived for random designs and Latin hypercube designs. The expectation and variance of Latin hypercube designs are significantly lower than that of random designs. While in dimension one the unique uniform design is also a set of equidistant points, low-discrepancy designs in higher dimension have to be generated by explicit optimization. Optimization is performed using the threshold accepting heuristic which produces low discrepancy designs compared to theoretic expectation and variance.

     

Completeness and Admissibility for General Heuristic Search Algorithms—A Theoretical Study: Basic Concepts and Proofs

We propose a formal generalization for various works dealing with Heuristic Search in State Graphs. This generalization focuses on the properties of the evaluation functions, on the characteristics of the state graphs, on the notion of path length, on the procedures that control the node expansions, on the rules that govern the update operations. Consequently, we present the algorithm family and the sub-family Ã, which include Nilsson's A or A_* and many of their successors such as HPA, B, A ^* , A, C, BF^*, B, IDA^*, D, A^**, SDW. We prove general theorems about the completeness and the sub-admissibility that widely extend the previous results and provide a theoretical support for using diverse kinds of Heuristic Search algorithms in enlarged contexts, specially when the state graphs and the evaluation functions are less constrained than ordinarily.     

Clustering for routing in densely populated areas

This paper introduces a new approach for generating school bus routes in a dense urban area. First, a districting algorithm is used to determine clusters including appropriate numbers of students. Then, for each cluster, a route and the stops along this route are determined. Numerical results are reported and compared with those obtained previously. Although the algorithm has been developped and tested in a specific context, it could easily be extended to more general vehicle routing problems.     

Non-classical preference models in combinatorial problems: Models and algorithms for graphs

This is a summary of the most important results presented in the authors PhD thesis (Spanjaard 2003). This thesis, written in French, was defended on 16 December 2003 and supervised by Patrice Perny. A copy is available from the author upon request. This thesis deals with the search for preferred solutions in combinatorial optimization problems (and more particularly graph problems). It aims at conciliating preference modelling and algorithmic concerns for decision aiding.Received: March 2004, MSC classification: 91B06, 90C27, 90B40, 16Y60     

A MIP approach for some practical packing problems: Balancing constraints and tetris-like items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.Received: September 2003, Revised: February 2004, AMS classification: 90B99, 05B40, 90C90, 90C59Thanks are due to T. A. Ciriani for the important suggestions given for the whole paper and to S. Gliozzi (IBM, Business Consulting Services) for the significant support offered, in particular in discussing the topics presented in Sect. 2.1.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

Even-aged restrictions with sub-graph adjacency

Restrictions on the size and proximity of clearcuts have led to the development of a variety of exact and heuristic methods to optimize the net present value of timber harvests, subject to adjacency constraints. Most treat harvest units as pre-defined, and impose adjacency constraints on any two units sharing a common border. By using graph theory notation to define sub-graph adjacency constraints, opening size can be considered variable, which may be more appropriate for landscape-level planning. A small example data set is used in this paper to demonstrate the difference between the two types of adjacency constraints for both integer programming and heuristic solution methods.     

Scheduling Tasks on Unrelated Machines: Large Neighborhood Improvement Procedures

Two approximation algorithms are presented for minimizing the makespan of independant tasks assigned on unrelated machines. The first one is based upon a partial and heuristical exploration of a search tree, which is used not only to build a solution but also to improve it thanks to a post-optimization procedure. The second implements a new large neighborhood improvement procedure to an already existing algorithm. Computational experiments show that their efficiency is equivalent to the best local search heuristics.     

Spatial competition facility location models: Definition,formulation and solution approach

Models are presented for locating a firm's production facilities and determining production levels at these facilities so as to maximize the firm's profit. These models take into account the changes in price at each of the spatially separated markets that would result from the increase in supply provided by the new facilities and also from the response of competing firms. Two different models of spatial competition are presented to represent the competitive market situation in which the firm's production facilities are being located. These models are formulated as variational inequalities; recent sensitivity analysis results for variational inequalities are used to develop derivatives of the prices at each of the spatially separated markets with respect to the production levels at each of the new facilities. These derivatives are used to develop a linear approximation of the implicit function relating prices to productions. A heuristic solution procedure making use of this approximation is proposed.