Search

A variant of the hub location routing problem studied in this work, which is the problem of locating a set of hub nodes, is establishing the hub-level network and allocating the spoke nodes to the hub nodes. As a particular property of this problem, each cluster of spoke nodes allocated to a hub constitutes a directed route that starts from the hub, visits all the spokes in the same cluster, and terminates to the same hub. We propose a hybrid of hyper-heuristic and a relax-and-cut solution method, which includes cooperation among several low-level heuristics governed and controlled by a learning mechanism. This hybridization provides a mechanism in which the obtained dual information through the Lagrangian relaxation (bundle) method being utilized to guide the local searches for constructing/improving feasible solutions. Several classes of valid inequalities as well as efficient separation routings are also proposed for being used within the relax-and-cut approach. Our extensive computational experiments confirm the efficiency of this solution method in terms of quality as well as computational time.

International audience; This paper introduces the selective traveling salesman problem with draft limits, an extension of the traveling salesman problem with draft limits, wherein the goal is to design a maximum profit tour respecting draft limit constraints at the visited nodes. We propose a mixed integer linear programming (MILP) formulation for this problem. This MILP model is used to solve—to optimality—small size instances and to assess the quality of solutions obtained using a general variable neighborhood search heuristic that explores several neighborhood structures. Our extensive computational experiments confirm the efficiency of the method and the quality of the reported solutions.

In this paper we address unbalanced spatial distribution of hub-level flows in an optimal hub-and-spoke network structure of median-type models. Our study is based on a rather general variant of the multiple allocation hub location problems with fixed setup costs for hub nodes and hub edges in both capacitated and uncapacitated variants wherein the number of hub nodes traversed along origin-destination pairs is not constrained to one or two as in the classical models.. From the perspective of an infrastructure owner, we want to make sure that there exists a choice of design for the hub-level sub-network (hubs and hub edges) that considers both objectives of minimizing cost of transportation and balancing spatial distribution of flow across the hub-level network. We propose a bi-objective (transportation cost and hub-level flow variance) mixed integer non-linear programming formulation and handle the bi-objective model via a compromise programming framework. We exploit the structure of the problem and propose a second-order conic reformulation of the model along with a very efficient matheuristics algorithm for larger size instances.

A novel mathematical model for the workover rig scheduling.Identifying several classes of valid inequalities.Developed a very efficient hyper-heuristic method.Developed a branch, price and cut algorithm for the problem.Work is based on a case study of Petrobras, Brazilian petroleum company. We take into account a parallel heterogenous machine scheduling problem arising in maintenance planning of heterogeneous wells. This problem particularly arises in the context of workover rig scheduling. The oil wells need regular maintenance to ensure an optimal level of production. After oil production being decreased at some wells, appropriate workover rigs with compatible service capacity, are deployed to serve the wells at discrete locations. Every well needs a certain level of maintenance and rehabilitation services that can only be offered by compatible workover rigs. A new mixed integer linear programming model is propose for this problem that is an arc-time-indexed formulation. We propose a heuristic selection type hyper-heuristic algorithm, which is guided by a learning mechanism resulting in a clever choice of moves in the space of heuristics that are applied to solve the problem. The output is then used to warm start a branch, price and cut algorithm. Our numerical experiments are conducted on instances of a case study of Petrobras, the Brazilian National Petroleum Corporation. The computational experiments prove the efficiency of our hyper-heuristic in searching the right part of the search space using the right alternation among different heuristics and confirms the high quality of solutions obtained by our hyper-heuristic.

We present an integrated modelling framework for the joint problems of network design, fleet deployment and empty repositioning in liner shipping. In our problem the number of service routes and their design are an endogenous part of the problem. The cost of a route is a set function mapping a subset of edges, vessel types and quantities to deploy to the set of non-negative real numbers. Since such cost structures cannot be accommodated in a compact formulation, our modelling framework, which is based on the paradigm of the Benders reformulation, integrates separate problems aiming to obtain a solution to the integrated problem. In this work we look at the Benders approach as a tool for integrating separate optimization problems rather than decomposing an integrated holistic optimization problem. Our numerical experiments show that the method is very efficient in solving instances of this problem with respect to both the problem size and the computational time.

A new mathematical model is proposed for the Ring Spur Assignment Problem (RSAP) that arises in the design of next-generation telecommunication networks. In this problem, every node of the network lies either on a ring among a set of bounded disjoint local rings or is spurred by a single arc to another node on a local ring. A special ring, called a tertiary ring, interconnects the local rings. Our new integer programming model employs only O ( n 2 ) variables and has a stronger LP relaxation. Several classes of valid inequalities and corresponding separation procedures are presented giving rise to an efficient branch-and-cut solution algorithm. We report optimal solutions for all SNDLib instances including those that have not previously been solved to optimality.

All shipping liner companies divide their service regions into several rotations (strings) in order to operate their container vessels. A string is the ordered set of ports at which a container vessel will call. Each port is usually called at no more than twice along one string, although a single port may be called at several times on different strings. The size of string dictates the number of vessels required to offer a given frequency of service. In order to better use their shipping capacity, groups of Liner Service Providers sometimes make a short term agreement to merge some of their service routes (in a certain region) into one main ocean going rotation and p feeder rotations. In order to minimize the weighted sum of transit time, and fixed deployment costs, this paper proposes a mixed integer linear programming model of the network design, and an allocation of proper capacity size and frequency setting for every rotation. Given that none of the existing general-purpose MIP solvers is able to solve even very small problem instances in a reasonable time, we propose a Lagrangian decomposition approach which uses a heuristic procedure and is capable of obtaining practical and high quality solutions in reasonable times. The model will be applied on a real example, and we shall present some of the results obtained by our model which show how it facilitates a better use of assets and a significant reduction in the use of fuel, therefore allowing a more environmentally friendly service.

International audience; In this paper, we present the first model of co-opetition for a Hub Location Problem between two logistics service provider (LSPs) companies where the mother company is the owner of infrastructure. The LSPs would like to cooperate with each other by establishing joint edges with limited capacities connecting their service networks. Such services are in form of pendulum services (a direct service between two points) between nodes of different networks. Additional market can be generated as a result of joining the two networks. At the same time, a competition is taking place between the two operators to increase their share from the additional market generated. In order to solve this problem, we propose a matheuristic approach combining a local search algorithm and a Lagrangian relaxation-based approach. In our matheuristic algorithm, the neighbourhood solutions are evaluated using a Lagrangian relaxation-based approach. Numerical results of applying the proposed algorithm on a real case study of the problem are presented.

International audience; In this paper, we address a truck dock assignment problem with operational time constraint which has to be faced in the management of cross docks. More specifically, this problem is the subproblem of more involved problems with additional constraints and criteria. We propose a new integer programming model for this problem. The dimension of the polytope associated with the proposed model is identified by introducing a systematic way of generating linearly independent feasible solutions. Several classes of valid inequalities are also introduced. Some of them are proved to be facet-defining. Then, exact separation algorithms are described for separating cuts for classes with exponential number of constraints, and an efficient branch-and-cut algorithm solving real-life size instances in a reasonable time is provided. In most cases, the optimal solution is identified at the root node without requiring any branching.

International audience; We propose an efficient heuristic approach for solving instances of the Single String Planning Problem (SSPP) arising in the liner shipping industry. In the SSPP a Liner Service Provider (LSP) only revises one of its many operational strings, and it is assumed that the other strings are unchangeable. A string is a service route composed of a sequence of port calls—a call is a visit to a port followed by loading/ unloading operations made by a vessel. In a string the vessel's round trip terminates at the same port that it started from, and the port calls follow a published itinerary. The SSPP is regularly encountered by all LSPs, and a major part of their seasonal network planning process is devoted to repeatedly solving SSPP for different regions using experts' knowledge. Despite the practical importance of the problem, very little has been written about it in the literature. A revision is carried out in the form of a controlled re-sequencing, insertion and elimination of ports from along the current string, given a set of ports limited to those that exist on the string and a set of potential ones. The outcome determines the required capacity, service level (frequency), call sequence, etc., corresponding to the LSP's seasonal strategy. Exact decomposition methods are limited and can solve only very small size instances—small in terms of the number of ports, vessel classes, vessel number and commodities. In contrast, the proposed heuristic method is an efficient approach for obtaining high quality and practical solutions to real-size instances in significantly less computational time.