Section: New Results

Large scale complex structure optimization

Formulation and algorithms for last-mile delivery systems:

E-commerce is a thriving market around the world and suits very well the busy lifestyle of today's customers and this growing e-commerce poses a huge challenge for transportation companies, especially in the last mile delivery. We addressed first a fleet composition problem for last-mile delivery service. This problem occurs at a tactical level when the composition of the fleet has to be decided in advance. It is the case for companies that offer last-mile delivery service. Most of them subcontract the transportation part to local carriers and have to decide the day before which vehicles will be needed to cover a partially known demand. We assumed that the distribution area is divided into a limited number of delivery zones and the time horizon into time-slots. The demand is characterized by packages to be transported from pick-up zones to delivery zones given a delivery time slot. First, we introduced an integer programming model which aims to minimize the total delivery cost while ensuring that the demand is covered, the capacity of each vehicle is not violated, the working time for each period is not exceeded and the total working of each delivery respects the social regulations. Then we present a column-generation based approach, which is able to solve real-life instances in reasonable CPU times [33], [32]. Nowadays, the most common last mile delivery service is home delivery. Besides home delivery, companies like Amazon and Fedex, develop locker delivery. When customers shop online, they can choose a nearby locker as a pickup location. In the past years, a new concept called trunk delivery, has been proposed. Here, customers' orders can be delivered to the trunk of their cars. We jointly considered all these delivery possibilities in the same last-mile system and studied the case where the fleet is limited to a single vehicle. We proposed different formulations for the rising optimization problem. We developed problem defined cuts in order to strengthen the formulations and be able to tackle real-size instances. Last we designed and implemented a branch-and-cut algorithm [55], [53].

Large neighborhood algorithm for multi-commodity vehicle routing problem: When delivering fresh fruits and vegetables to catering the multi commodity aspect should be taken into account and deliveries to customers are not made in once, but each commodity can be delivered by a different vehicle as long as the total demand of that commodity is delivered. The problem that arises is the commodity constrained split delivery vehicle routing problem (C-SDVRP). We propose a heuristic based on the adaptive large neighborhood search (ALNS) to efficiently solve medium and large sized instances of the C-SDVRP. We take into account the distinctive features of the C-SDVRP and adapt several local search moves to improve a solution. Moreover, a mathematical programming based operator (MPO) that reassigns commodities to routes is used to improve a new global best solution. Computational experiments have been performed on benchmark instances from the literature. The results assess the efficiency of the algorithm, which can provide a large number of new best-known solutions in short computational times [50].

A matheuristic for the packaging and shipping problem: E-commerce has been continuously growing in the last years to a primary retail market. Recently in France, the threshold of 1 billion of online transactions was overcome. Due to a high demand fluctuation of e-commerce, the workforce sizing for the logistic chain is a challenging problem. Companies have to develop good strategies to have a sustainable workforce size while guaranteeing a high-level service. In this work, we consider the management of the workforce for a warehouse of an e-commerce company. Specifically, we address issues as i) How the workforce at the warehouse can be determined; ii) What is the daily operational production planning; iii) How the demand peaks can be smoothed, and the production maintained ideally constant over the time horizon. To provide answers to these issues, we introduce the Packaging and Shipping Problem (PSP). The PSP looks for a solution approach that jointly determines the workforce over a multi-period horizon and daily operational plans while minimizing the total logistics cost. We consider two strategies that aim to enhance the flexibility of the process and the efficiency of resources use: reassignment and postponement. To tackle the Packaging and Shipping Problem we propose a model, and a three-phase matheuristic. This heuristic is proved to be competitive with respect to the direct solution of the model with a commercial solver on real-life based instances [18].

Heuristic and column generation approaches for the joint order batching and picker routing problem: Picking is the process of retrieving products from the inventory. It is mostly done manually by dedicated employees called pickers and is considered the most expensive of warehouse operations. To reduce the picking cost, customer orders can be grouped into batches that are then collected by traveling the shortest possible distance. We proposed an industrial case study for the HappyChic company where the warehouse has an acyclic layout: pickers are not allowed to backtrack. We developed a two-phase heuristic approach to solve this industrial case [59]. Moreover, we proposed an exponential linear programming formulation to tackle the joint order batching and picker routing problem. Variables, or columns, are related to the picking routes in the warehouse. Computing such routes is in general an intractable routing problem and relates to the well known traveling salesman problem (TSP). Nonetheless, the rectangular warehouse’s layouts can be used to efficiently solve the corresponding TSP. Experimented on a publicly available benchmark, the algorithm proves to be very effective. It improves many of the best known solutions and provides very strong lower bounds. This approach is also applied to the HappyChic industrial case to demonstrate its interest for this field of application [41].

Distribution network configuration problems: A distribution network is a system aiming to transfer a certain type of resource from feeders to customers. Feeders are producers of a resource and customers have a certain demand in this resource that must be satisfied. Distribution networks can be represented on graphs and be subject to constraints that limit the number of intermediate nodes between some elements of the network (hop constraints) because of physical constraints. We used layered graphs for hop constrained problems to build extended formulations [21]. Preprocessing techniques allowed to reduce the size of the layered graphs used. The model was studied on the hop-constrained minimum margin problem in an electricity network. This problem consists of designing a connected electricity distribution network, and to assign customers to electricity feeders at a maximum number of hops H so as to maximize the minimum capacity margin over the feeders to avoid an overload for any feeder. A related theoretical work considers a very special case of hop constrained network design, namely the 2 edge-disjoint 3-paths polyhedron [15].

Switched Ethernet network design problems: We studied models arising in the design of switched Ethernet networks implementing the Multiple Spanning Tree Protocol [23]. In these problems, multiple spanning trees have to be established in a network to route demands partitioned into virtual local access networks. Different mixed-integer formulations for the problem have been proposed and compared, both theoretically and computationally.

Delay management in public transportation: The Delay Management Problem arises in Public Transportation networks, and is characterized by the necessity of connections between different vehicles. The attractiveness of Public Transportation networks is strongly related to the reliability of connections, which can be missed when delays or other unpredictable events occur. Given a single initial delay at one node of the network, the Delay Management Problem is to determine which vehicles have to wait for the delayed ones, with the aim of minimizing the dissatisfaction of the passengers. We derived strengthened mixed integer linear programming formulations and new families of valid inequalities for that problem. The implementation of branch-and-cut methods and tests on a benchmark of instances taken from real networks show the potential of the proposed formulations and cuts [20].

Discrete ordered median problem: The discrete ordered median problem consists in locating $p$ facilities in order to minimize an ordered weighted sum of distances between clients and closest open facility. We formulate this problem as a set partitioning problem using an exponential number of variables. Each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding costs. We develop a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-price-and-cut algorithm to solve small to large sized instances of DOMP in competitive computational time [62].

Genome wide association studies: We studied the Polymorphic Alu Insertion Recognition Problem (PAIRP). Alu (Arthrobacter luteus) forms a major component of repetitive DNA and are frequently encountered during the genotyping of individuals. The basic approach to find Alus consists of (i) aligning sequence reads from a set of individual(s) with respect to a reference genome and (ii) comparing the possible Alu insertion induced by the alignment with the Alu insertions positions already known for the reference genome. The sequence genome of the reference individual is known and will be highly similar, but not identical, to the genome of the individual(s) being sequenced. Hence, at some locations they will diverge. Some of this divergence is due to the insertion of Alu polymorphisms. Detecting Alus has a central role in the field of Genetic Wide Association Studies because basic elements are a common source of mutation in humans. We investigated the PAIRP relationship with the the Clique Partitioning of Interval Graphs (CPIG). Our results [12], [26] provide insights of the complexity of the problem, a characterization of its combinatorial structure and an exact approach based on Integer Linear Programming to exactly solve the correspond instances.

A branch-and-cut algorithm for the maximum $k$-balanced subgraph of a signed graph: A signed graph is $k$-balanced if its vertex set can be partitioned into at most $k$ sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum $k$-balanced subgraph problem is the problem of finding a subgraph of G that is $k$-balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative vs conflicting environments. We provide a representatives formulation for the problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work [22].

Feature selection in support vector machine: This work focuses on support vector machine (SVM) with feature selection. A MILP formulation is proposed for the problem. The choice of suitable features to construct the separating hyperplanes has been modelled in this formulation by including a budget constraint that sets in advance a limit on the number of features to be used in the classification process. We propose both an exact and a heuristic procedure to solve this formulation in an efficient way. Finally, the validation of the model is done by checking it with some well-known data sets and comparing it with classical classification methods [25].