A multi-phase heuristic for the production routing problem

This study considers the production routing problem where a plant produces and distributes a single item to multiple retailers over a multi-period time horizon. The problem is to decide on when and how much to produce and stock at the plant, when and how much to serve and stock at each retailer, and vehicle routes for shipments such that the sum of fixed production setup cost, variable production cost, distribution cost, and inventory carrying cost at the plant and retailers is minimized. A multi-phase heuristic is proposed for the problem. The proposed heuristic is a mathematical programming-based heuristic that relies on formulating and solving restricted versions of the problem as mixed integer programs. The computational experiments on benchmark instances show favorable results with regard to the quality of the solutions found at the expense of higher computing times on large instances. In particular, the heuristic managed to find new best solutions for the 65% of benchmark instances.     

Generalized mixed integer and VNS heuristic approach to solving the multisize containers drayage problem

This paper addresses the problem of vehicle routing in drayage operations, where vehicles can carry containers of different sizes. The multisize container drayage problem with time windows is modeled as a multiple matching problem and formulated as a mixed integer linear program (MILP) model. The proposed MILP model determines optimal pickup and delivery routes of vehicles and is applicable to any type of vehicles capable of simultaneously transporting any arbitrary number of 20‐ and 40‐ft containers. To solve larger sized problems, we proposed a variable neighborhood search (VNS) heuristic. Both MILP and VNS approaches have been tested on numerous test instances and their performances are reported.     

Joint gateway selection,transmission slot assignment,routing and power control for wireless mesh networks

Wireless mesh networks (WMNs) provide cost effective solutions for setting up a communications network over a certain geographic area. In this paper, we study strategic problems of WMNs such as selecting the gateway nodes along with several operational problems such as routing, power control, and transmission slot assignment. Under the assumptions of the physical interference model and the tree-based routing restriction for traffic flow, a mixed integer linear programming (MILP) formulation is presented, in which the objective is to maximize the minimum service level provided at the nodes. A set of valid inequalities is derived and added to the model in an attempt to improve the solution quality. Since the MILP formulation becomes computationally infeasible for larger instances, we propose a heuristic method that is aimed at solving the problem in two stages. In the first stage, we devise a simple MILP problem that is concerned only with the selection of gateway nodes. In the second stage, the MILP problem in the original formulation is solved by fixing the gateway nodes from the first stage. Computational experiments are provided to evaluate the proposed models and the heuristic method.     

A heuristic algorithm for optimal fleet composition with vehicle routing considerations

This paper proposes a fast heuristic algorithm for solving a combined optimal fleet composition and multi-period vehicle routing problem. The aim of the problem is to determine an optimal fleet mix, together with the corresponding vehicle routes, to minimize total cost subject to various customer delivery requirements and vehicle capacity constraints. The total cost includes not only the fixed, variable, and transportation costs associated with operating the fleet, but also the hiring costs incurred whenever vehicle requirements exceed fleet capacity. Although the problem under consideration can be formulated as a mixed-integer linear program (MILP), the MILP formulation for realistic problem instances is too large to solve using standard commercial solvers such as the IBM ILOG CPLEX optimization tool. Our proposed heuristic decomposes the problem into two tractable stages: in the first (outer) stage, the vehicle routes are optimized using cross entropy; in the second (inner) stage, the optimal fleet mix corresponding to a fixed set of routes is determined using dynamic programming and golden section search. Numerical results show that this heuristic approach generates high-quality solutions and significantly outperforms CPLEX in terms of computational speed.     

Production scheduling and vehicle routing with time windows for perishable food products

We propose a nonlinear mathematical model to consider production scheduling and vehicle routing with time windows for perishable food products in the same framework. The demands at retailers are assumed stochastic and perishable goods will deteriorate once they were produced. Thus the revenue of the supplier is uncertain and depends on the value and the transaction quantity of perishable products when they are carried to retailers. The objective of this model is to maximize the expected total profit of the supplier. The optimal production quantities, the time to start producing and the vehicle routes can be determined in the model simultaneously. Furthermore, we elaborate a solution algorithm composed of the constrained Nelder–Mead method and a heuristic for the vehicle routing with time windows to solve the complex problem. Computational results indicate our algorithm is effective and efficient.     

A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods

We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D’Andreagiovanni, 2012), a refinement of classical Γ-Robustness by Bertsimas and Sim that uses a system of multiple deviation bands.Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.     

Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery

In this paper we observe the extension of the vehicle routing problem (VRP) in fuel delivery that includes petrol stations inventory management and which can be classified as the Inventory Routing Problem (IRP) in fuel delivery. The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. We developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies with each petrol station and each fuel type. The stochastic VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic “compartment transfer” (CT) heuristic. For three different scale problems, with different vehicle types, the developed VNS heuristic outperforms the deterministic CT heuristic. Also, for the smallest scale problem instances, the developed VNS was capable of obtaining the near optimal and optimal solutions (the MILP model was able to solve only the smallest scale problem instances).     

Multi-product valid inequalities for the discrete lot-sizing and scheduling problem

We consider a problem arising in the context of industrial production planning, namely the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs. We aim at developing an exact solution approach based on a Cut & Branch procedure for this combinatorial optimization problem. To achieve this, we propose a new family of multi-product valid inequalities which corresponds to taking into account the conflicts between different products simultaneously requiring production on the resource. We then present both an exact and a heuristic separation algorithm which form the basis of a cutting-plane generation algorithm. We finally discuss computational results which confirm the practical usefulness of the proposed inequalities at strengthening the MILP formulation and at reducing the overall computation time.     

Solving the ship inventory routing and scheduling problem with undedicated compartments

This paper presents a ship inventory routing and scheduling problem with undedicated compartments (sIRPSP-UC). The objective of the problem is to find a minimum cost solution while satisfying a number of technical and physical constraints within a given planning horizon. In this problem, we identify four sub-problems that need to be decided simultaneously: route selections, ship selection, loading, and unloading activity procedures. To solve this problem, first, we developed a mixed integer linear programming model. We then developed a one-step greedy heuristic, and then based on this heuristic, we propose a set of heuristics. Each heuristic has a combination of rules for each sub-problem. A number of problem instances are used to compare the solutions of the two approaches. We applied selected good combinations of rules to solve each problem using the heuristic approach. The results show that 8 out 12 of the considered problem instances have no gap with MILP solution solved using LINGO. We also find that the average gap is 1.96%. In contrast when we consistently use the same combination for all iterations, there are no dominant combinations of heuristics that can find good solutions for all the problem instances.     

Solving mixed integer programming production planning problems with setups by shadow price information

Algorithms developed to solve linear programming (LP) problems and advances in computer speed have made large-scale LP problems solvable in time for implementation. Solving an LP is relatively easier than solving an MIP for modern production planning problems. In this study, we propose a heuristic iterative algorithm between LP solution phases and setup decision computations for solving these difficult MIP production planning problems. By utilizing the shadow price information provided by the LP solution of the previous iteration, the setup decision computation converts an MIP problem into an LP problem, which can be efficiently solved in the current iteration. Extensive experiments show that the proposed heuristic algorithm performs well.     

A bi-level evolutionary optimization approach for integrated production and transportation scheduling

This paper investigates an integrated production and transportation scheduling (IPTS) problem which is formulated as a bi-level mixed integer nonlinear program. This problem considers distinct realistic features widely existing in make-to-order supply chains, namely unrelated parallel-machine production environment and product batch-based delivery. An evolution-strategy-based bi-level evolutionary optimization approach is developed to handle the IPTS problem by integrating a memetic algorithm and heuristic rules. The efficiency and effectiveness of the proposed approach is evaluated by numerical experiments based on industrial data and industrial-size problems. Experimental results demonstrate that the proposed approach can effectively solve the problem investigated.     

Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

Planning production using mathematical programming: The case of a woodturning company

Herein we present a case of production planning in a woodturning company. The company wishes to plan the turning of various types of products of different radii in a set of parallel machines (lathes) and with the following principal conditions: for each type of product there is a minimum production lot size; some lathes cannot manufacture every type of product; the production capacity of a lathe depends on the lathe itself and the type of product to be manufactured; the products are classified into families according to radius; and there is an intra-family setup time (for manufacturing different products that have the same radius) and an inter-family setup time (for consecutively manufacturing products that have different radii), which is longer; part of the production can be subcontracted; each type of product can be manufactured on different lathes and/or subcontracted; and the operators can work overtime, during which additional time they can simultaneously operate multiple lathes. The goal is to meet the demand at minimum cost, which includes the cost of any overtime plus that of any subcontracting. The problem was modelled and solved by mixed-integer linear programming (MILP). The company considers the results to be satisfactory.     

Battery swap station location-routing problem with capacitated electric vehicles

In this paper, we present an electric vehicles battery swap stations location routing problem (BSS–EV–LRP), which aims to determine the location strategy of battery swap stations (BSSs) and the routing plan of a fleet of electric vehicles (EVs) simultaneously under battery driving range limitation. The problem is formulated as an integer programming model under the basic and extended scenarios. A four-phase heuristic called SIGALNS and a two-phase Tabu Search-modified Clarke and Wright Savings heuristic (TS-MCWS) are proposed to solve the problem. In the proposed SIGALNS, the BSSs location stage and the vehicle routing stage are alternated iteratively, which considers the information from the routing plan while improving the location strategy. In the first phase, an initial routing plan is generated with a modified sweep algorithm, leading to the BSSs location subproblem, which is then solved by using an iterated greedy heuristic. In the third phase, the vehicle routes resulting from the location subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. At the end of SIGALNS, the solution is further improved by a split procedure. Compared with the MIP solver of CPLEX and TS-MCWS over three sets of instances, SIGALNS searches the solution space more efficiently, thus producing good solutions without excessive computation on the medium and large instances. Furthermore, we systematically conduct economic and environmental analysis including the comparison between basic and extended scenarios, sensitivity analysis on battery driving range and efficiency analysis about the vehicle emissions reduction when EVs are used in the logistics practice.     

A branch-and-price algorithm for an integrated production and inventory routing problem

With globalization, the need to better integrate production and distribution decisions has become ever more pressing for manufacturers trying to streamline their supply chain. This paper investigates a previously developed mixed-integer programming (MIP) model aimed at minimizing production, inventory, and delivery costs across the various stages of the system. The problem being modeled includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of homogeneous vehicles. Demand can be satisfied from either inventory held at a customer site or from daily product distribution. Whether a customer is visited on a particular day is determined by an implicit tradeoff between inventory and distribution costs. Once the decision is made, a vehicle routing problem must be solved for those customers who are scheduled for a delivery.A hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework is developed to solve the underlying MIP. The approach takes advantage of the efficiency of heuristics and the precision of branch and price. Implementation required devising a new branching strategy to accommodate the unique degeneracy characteristics of the master problem, and a new procedure for handling symmetry. A novel column generation heuristic and a rounding heuristic were also implemented to improve algorithmic efficiency. Computational testing on standard data sets showed that the hybrid scheme can solve instances with up to 50 customers and 8 time periods within 1 h. This level of performance could not be matched by either CPLEX or standard branch and price alone.     

A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

Local search techniques for a routing-packing problem

We propose a complex real-world problem in logistics that integrates routing and packing aspects. It can be seen as an extension of the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) introduced by Gendreau, Iori, Laporte, and Martello (2006). The 3L-CVRP consists in finding a set of routes that satisfies the demand of all customers, minimizes the total routing cost, and guarantees a packing of items that is feasible according to loading constraints. Our problem formulation includes additional constraints in relation to the stability of the cargo, to the fragility of items, and to the loading and unloading policy. In addition, it considers the possibility of split deliveries, so that each customer can be visited more than once. We propose a local search approach that considers the overall problem in a single stage. It is based on a composite strategy that interleaves simulated annealing with large-neighborhood search. We test our solver on 13 real-world instances provided by our industrial partner, which are very diverse in size and features. In addition, we compare our solver on benchmarks from the literature of the 3L-CVRP showing that our solver performs well compared to other approaches proposed in the literature.     

A decision support system for optimizing dynamic courier routing operations

In this paper, we propose a prototype of a decision support system (DSS) that integrates a hybrid neighborhood search algorithm to solve the offline and online routing problems arising in courier service. In the dynamic operational environment of courier service, new customer orders and order cancellations continually arrive over time and thus disrupt the optimal routing schedule that was originally designed. This calls for the real-time re-optimization of routes. As service level is sensitive to whether allowable service time intervals are wide or narrow, it is valuable to study how adjustable and flexible time windows influence the courier service efficiency in a dynamic environment. To capture these dynamic features, a dynamic vehicle routing problem (DVRP) that simultaneously considers new customer orders and order cancellations is investigated in this study. Meanwhile, fuzzy time windows are formulated in the DVRP model to quantify the service level and explore the service efficiency. To tackle the new problem, we propose a competitive hybrid neighborhood search heuristic for (re)optimizing the offline and online routes. Numerical computational experiments and the comparison with results from Lingo show that our algorithm is capable of re-optimizing dynamic problems effectively and accurately in a very short time. The proposed model and algorithms are able to enhance courier service level without further expense of a longer traveling distance or a larger number of couriers.     

Maintenance costs and makespan minimization for assembly permutation flow shop scheduling by considering preventive and corrective maintenance

The joint optimization of production scheduling and maintenance planning has a significant influence on production continuity and machine reliability. However, limited research considers preventive maintenance (PM) and corrective maintenance (CM) in assembly permutation flow shop scheduling. This paper addresses the bi-objective joint optimization of both PM and CM costs in assembly permutation flow shop scheduling. We also propose a new mixed integer linear programming model for the minimization of the makespan and maintenance costs. Two lemmas are inferred to relax the expected number of failures and CM cost to make the model linear. A restarted iterated Pareto greedy (RIPG) algorithm is applied to solve the problem by including a new evaluation of the solutions, based on a PM strategy. The RIPG algorithm makes use of novel bi-objective-oriented greedy and referenced local search phases to find non-dominated solutions. Three types of experiments are conducted to evaluate the proposed MILP model and the performance of the RIPG algorithm. In the first experiment, the MILP model is solved with an epsilon-constraint method, showing the effectiveness of the MILP model in small-scale instances. In the remaining two experiments, the RIPG algorithm shows its superiority for all the instances with respect to four well-known multi-objective metaheuristics.