A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

Facilitated modelling in operational research

The traditional way of employing operational research in organisational interventions has been the expert mode. In this mode, the problem situation faced by the client is given to the operational research consultant, who then builds a model of the situation, solves the model to arrive at an optimal (or quasi-optimal) solution, and then provides a recommendation to the client based on the obtained solution. An alternative mode of engagement is to conduct the whole intervention together with the client: from structuring and defining the nature of the problem situation of interest, to supporting the evaluation of priorities and development of plans for subsequent implementation. In this latter mode, the operational researcher works throughout the intervention not only as an analyst, but also as a facilitator to the client. This paper discusses this latter mode of engagement with clients, with particular emphasis on the use of facilitated modelling as the intervention tool. Drawing on research scattered across a range of publications and domains, the review presented here provides a formal definition of facilitated modelling, together with a general framework that allows the conceptualisation of a wide variety of facilitated modelling approaches to organisational intervention. Design issues in facilitated modelling and their practical implication are discussed, and directions for future research identified.     

Constant memory routing in quasi-planar and quasi-polyhedral graphs

We address the problem of online route discovery for a class of graphs that can be embedded either in two or in three-dimensional space. In two dimensions we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In the former case such graphs are geometrically embedded in R² and have an underlying backbone that is planar with convex faces; however within each face arbitrary edges (with arbitrary crossings) are allowed. In the latter case, these graphs are geometrically embedded in R³ and consist of a backbone of convex polyhedra and arbitrary edges within each polyhedron. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only “remember” the source and destination nodes and one (respectively, two) reference nodes used to store information about the underlying face (respectively, polyhedron) currently being traversed. The existence of the backbone is used only in proofs of correctness of the routing algorithm; the particular choice is irrelevant and does not affect the behaviour of the algorithm.     

A facility location and installation of resources model for level of repair analysis

The Level of Repair Analysis – LORA – is an analytic methodology aimed at determining: (i) the optimal location of facilities that compose a maintenance structure; (ii) the quantity of required resources in each facility; and (iii) the best repair policies, i.e., rules that determine if a given component should be discarded or repaired, and where those actions should take place. This work presents a mixed-integer programming model for LORA that is more comprehensive than others in the literature, being suitable to many practical situations. The model was applied to 15 substantial real world problems, and considering distinct maintenance policies to some of them, resulted in 22 different solutions, all of which could be achieved by a commercial Mixed-Integer Programming (MIP) solver in reasonable times.     

Computing finest mincut partitions of a graph and application to routing problems

Let G=(V,E,w) be an n-vertex graph with edge weights w>0. We propose an algorithm computing all partitions of V into mincuts of G such that the mincuts in the partitions cannot be partitioned further into mincuts. There are O(n) such finest mincut partitions. A mincut is a non-empty proper subset of V such that the total weight of edges with exactly one end in the subset is minimal. The proposed algorithm exploits the cactus representation of mincuts and has the same time complexity as cactus construction. An application to the exact solution of the general routing problem is described.     

A heuristic for the multi-period petrol station replenishment problem

In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

A meta-model for multiobjective routing in MPLS networks

MPLS (Multiprotocol Label Switching) enables the utilisation of explicit routes and other advanced routing mechanisms in multiservice packet networks, capable of dealing with multiple and heterogeneous QoS (Quality of Service) parameters. Firstly the paper presents a discussion of conceptual and methodological issues raised by multiobjective routing optimisation models for MPLS networks. The major contribution is the proposal of a multiobjective routing optimisation framework for MPLS networks. The major features of this modelling framework are: the formulation of a three-level hierarchical routing optimisation problem including network and service performance objectives, the inclusion of fairness objectives in the different levels of optimisation and a two-level stochastic representation of the traffic in the network (traffic flow and packet stream levels). A variant of the general model for two classes of traffic flows, QoS traffic and Best Effort traffic, is also presented. Finally a stochastic teletraffic modelling approach, underlying the optimisation model, is fully described. Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

Safety and comfort analysis of a 3-D vehicle model with optimal non-linear active seat suspension

A generalized nonlinear model is formulated for the dynamic analysis of suspension seats with passive, semi-active and active dampers. The model incorporates coulomb friction due to suspension linkages and bushings, forces arising from interactions with the elastic limit stops, a linear suspension spring and nonlinear damping force for passive, semi-active and active dampers, while the contribution due to biodynamics of the human operator is considered to be negligible. The semi-active and active dampers are characterized by force generators in accordance with the control laws based upon suspension mass velocity. Two different suspension seats are experimentally assessed in the laboratory under sinusoidal and random excitations arising from an urban bus, and the measured data is used to demonstrate the validity of the proposed generalized model. The results showed reasonably good agreement between the model results and the measured data. Optimal model parameters are selected using the sequential unconstrained minimization technique with an objective to minimize the acceleration due to vibration transmitted to the occupant mass. The comfort and safety performance characteristics of the optimal suspension seat with semi-active and active dampers are evaluated under both the sinusoidal and random excitations based on the guidelines provided by ISO-2631. From these results, it is concluded that the comfort performance of a suspension seat with semi-active and active dampers can be considerably enhanced by 20–30%.     

无人机光电载荷图像处理器的设计

介绍了无人机载设备的技术特点及机载小型图像处理器的组成。采用TI公司的数字信号处理器芯片为核心处理器,配合现场可编程逻辑器件(FPGA)与外部管理微控制单元(MCU)来实现目标数据的采集与处理,设计了适用于无人机光电载荷的超小型图像处理器系统。针对机载设备的特点,设计时充分考虑了体积、重量、功耗等要求。该系统已应用于多台套机载光电载荷中,工作稳定可靠,满足无人侦察机对捕捉和定位目标的要求。