A Multi-Trip Vehicle Routing Problem With Release Dates and Interrelated Periods Raquel Bernardino, João Janela, Carlos Martins, Maria Cândida Mourão, Leonor Santiago Pinto, Filipe Rodrigues Networks, 2025 This article proposes a new multi‐trip vehicle routing problem variant, originally motivated by a practical application, namely a car components distribution to repair centers (warehouses). The problem is named the multi‐trip vehicle routing with release dates and interrelated periods (MTVRP‐RDIP). The routes may start at different pre‐defined periods, called departure periods, and may have different durations. Thus, two routes that start at different periods may be active at the same period, leading to the so‐called interrelated periods. Moreover, a route may only start at a period if a vehicle is available, and the availability of the vehicle depends not only on the existing vehicles but also on the active routes at that time period. The clients are classified according to their importance and represent warehouses that require car components that are made available throughout the time horizon, thus leading to the consideration of release dates. Delays in satisfying client orders and not serving orders in the time horizon result in penalty costs that must be minimized. The objective to minimize also includes routing costs and vehicle utilization costs. Two metrics are defined to compute an order's delay, each leading to a different mixed integer linear model. Computational results showed that one model clearly outperforms the other and even this one is only suited to address the smallest instances. A matheuristic based on a rolling‐horizon process that iteratively solves the better‐performing model with fewer periods was designed to tackle the largest instances. The matheuristic can provide feasible solutions for all test instances in an efficient manner that are, on average, better than the ones provided by the model in most of the compared key performance indicators.
Decomposition heuristics for multiobjective problems. The Food bank network redesign case C.L. Martins, M.V. Pato International Journal of Production Economics, 2024 Large MO-MILP problems are often very hard to solve by exact methods. In this study we consider the Food bank network redesign (FBNR) problem to introduce three decompose-and-fix heuristics that successfully solve large real-life based instances of the problem. The FBNR problem is modeled as a multi-period, multi-product supply chain redesign problem that accounts for economic, environmental and social objectives in three distinct functions. Each new heuristic decomposes the FBNR problem into two MO-MILP problems, which are sequentially solved following the lexicographic concept. Decomposition observe the nature and terms of the decisions involved. The first MO-MILP problem concerns only the longer term decisions. After the corresponding decisions are fixed, the second MO-MILP problem referring to shorter term decisions is solved respecting the ranking of objectives followed for each solution obtained in the first problem. The difference among the heuristics lies in what is considered as longer or shorter term decisions. Besides solving large instances of the problem, which the exact method used could not do, CPU time savings generated by the heuristics range from 80% to 97% of the time required by the exact method. Compromise between the computational effort and the quality of solutions obtained by each heuristic is discussed. The solving methodology proposed in this study can be adapted to other large multiobjective problems.
