Green logistics oriented tug scheduling for inland waterway logistics

Under the global consensus on reducing emissions, shipping companies are undertaking the social responsibility of greenhouse gas emission reduction. Meanwhile, it is a top priority for shipping companies to arrange the tugs and barges reasonably and achieve the goal of energy saving as well as emission reduction. Based on the above problem, this paper proposes a Mixed Integer Programming (MIP) model to jointly optimize the transport routes of tugs considering the barge transshipment, with the objective of minimizing the sum of the carbon emissions for barges handling, tugs travelling and waiting. In the view of specific problem, a Variable Neighborhood Search (VNS) algorithm is designed to solve this MIP model effectively. Numerical experiments based on different sizes of instances are implemented to validate the effectiveness of the proposed algorithm. Computational results indicate that the proposed model reduces carbon emissions by about 46.93% compared to the dispatching rule. Moreover, the consideration of barge transshipment in the model can reduce carbon emissions by about 10.46%. In addition, the VNS algorithm yields solutions with optimality gaps about 0.29% in a short time.     

Variable neighborhood search for the pharmacy duty scheduling problem

In this paper, we study on the Pharmacy Duty Scheduling (PDS) problem, where a subset of pharmacies should be on duty on national holidays, at weekends and at nights in order to be able to satisfy the emergency drug needs of the society. PDS problem is a multi-period p-median problem with special side constraints and it is an NP-Hard problem. We propose four Variable Neighborhood Search (VNS) heuristics. The first one is the basic version, BVNS. The latter two, Variable Neighborhood Decomposition Search (VNDS) and Variable Neighborhood Restricted Search (VNRS), aim to obtain better results in less computing time by decomposing or restricting the search space. The last one, Reduced VNS (RVNS), is for obtaining good initial solutions rapidly for BVNS, VNDS and VNRS. We test BVNS, VNRS and VNDS heuristics on randomly generated instances and report the computational test results. We also use VNS heuristics on real data for the pharmacies in central İzmir and obtain significant improvements.     

Auto tuning for new energy dispatch problem: A case study

The new energy dispatch problem has aroused more and more attention. In this paper, we investigate the problem of determining the optimal usage of generating power during a scheduling period. A set of MIP formulations are adopted for precise modeling of the variety of power systems (different power generation units) and the actual situation in china. Based on these formulations, we construct a new energy dispatch model which includes many MIP sub-problems. An auto-tuning MIP solver CMIP is given to effectively improve the performance of solving the proposed model. The CMIP focuses on optimizations for presolver, the LP solver for corresponding relaxation problem, and the primal heuristics. Actual predict data is used in performance experiments. Computational results conform to the viability of optimization. Our optimizations further reduce 27.6% of the average execution time compared to CPLEX.     

The optimization of warehouse location and resources distribution for emergency rescue under uncertainty

China is one of the countries that suffer the most natural disasters in the world. The situation of emergency response and rescue is extremely tough. Establishing the emergency warehouse is one of the important ways to cope with rapid-onset disasters. In this paper, a mixed integer programming (MIP) model based on time cost under uncertainty is proposed, which help solve the emergency warehouse location and distribution problem. Comprehensive consideration of factors such as time cost, penalty cost for lack of resources, alternative origins of resources from both suppliers and emergency warehouses, different means of transportation and multiple resources types are involved in our study. We also introduce uncertain scenarios to describe the severity of the disaster. Particle swarm optimization (PSO) and variable neighborhood search (VNS) are designed to solve the MIP model of different scales of instances. Numerous examples have been tested to compare two heuristics with commercial solver (CPLEX). Both of two algorithms can obtain the exact solution same as CPLEX in small-scale instances while show great performance on larger instances with 10 candidate warehouses, 25 disasters and 50 scenarios.     

A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan

A common assumption in the classical permutation flowshop scheduling model is that each job is processed on each machine at most once. However, this assumption does not hold for a re-entrant flowshop in which a job may be operated by one or more machines many times. Given that the re-entrant permutation flowshop scheduling problem to minimize the makespan is very complex, we adopt the CPLEX solver and develop a memetic algorithm (MA) to tackle the problem. We conduct computational experiments to test the effectiveness of the proposed algorithm and compare it with two existing heuristics. The results show that CPLEX can solve mid-size problem instances in a reasonable computing time, and the proposed MA is effective in treating the problem and outperforms the two existing heuristics.     

Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem

Recently several hybrid methods combining exact algorithms and heuristics have been proposed for solving hard combinatorial optimization problems. In this paper, we propose new iterative relaxation-based heuristics for the 0-1 Mixed Integer Programming problem (0-1 MIP), which generate a sequence of lower and upper bounds. The upper bounds are obtained from relaxations of the problem and refined iteratively by including pseudo-cuts in the problem. Lower bounds are obtained from the solving of restricted problems generated by exploiting information from relaxation and memory of the search process. We propose a new semi-continuous relaxation (SCR) that relaxes partially the integrality constraints to force the variables values close to 0 or 1. Several variants of the new iterative semi-continuous relaxation based heuristic can be designed by a given update procedure of multiplier of SCR. These heuristics are enhanced by using local search procedure to improve the feasible solution found and rounding procedure to restore infeasibility if possible. Finally we present computational results of the new methods to solve the multiple-choice multidimensional knapsack problem which is an NP-hard problem, even to find a feasible solution. The approach is evaluated on a set of problem instances from the literature, and compared to the results reached by both CPLEX solver and an efficient column generation-based algorithm. The results show that our algorithms converge rapidly to good lower bounds and visit new best-known solutions.     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

A variable neighborhood search algorithm for the surgery tactical planning problem

We address the tactical planning problem of surgeries that consists in building an admission plan of patients over a medium-term horizon planning so as to minimize over and under utilization of several resources such as operating theaters, beds and nursing care, compared with their target level of utilization. The problem is formulated as a mixed integer linear program for which exact solution methods fail to find an optimal solution in a reasonable execution time. We develop a Variable Neighborhood Search algorithm and show its ability to provide high quality solutions in short computational running times compared with CPLEX for numerous real-sized instances based on the surgery planning problem in a Dutch cardiothoracic center. Furthermore, with few parameters' settings and low computational memory requirements, this approach may easily be implemented in a decision support system for hospitals.     

Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

Variable neighbourhood decomposition search for 0–1 mixed integer programs

In this paper we propose a new hybrid heuristic for solving 0–1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods.     

A Variable MIP Neighborhood Descent algorithm for managing inventory and distribution of cash in automated teller machines

In this paper we propose a new hybrid algorithm to solve mixed-integer programming (MIP) models called Variable MIP Neighborhood Search (VMND). The VMND relies on an existing mathematical formulation of the problem and significantly accelerates its resolution compared to standalone MIP solvers. Using this algorithm, we solve a practical problem arising in the ATM management and replenishment in Santiago, Chile. This rich and challenging problem, which we call the inventory-routing problem with cassettes and stockouts, shares much of its structure with the inventory-routing problem, but some features make it unique. We exploit the structure of the problem to derive neighborhoods implemented in our VMND, be it over routes, locations, periods or quantities delivered. Based on extensive computational experiments, our VMND is shown to significantly outperform benchmark solutions from a branch-and-cut algorithm. A sensitivity analysis is performed to confirm the robustness and effectiveness of our method.     

Variable neighborhood search and local branching

In this paper we develop a variable neighborhood search (VNS) heuristic for solving mixed-integer programs (MIPs). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent local branching (LB) method of Fischetti and Lodi (Mathematical Programming Series B 2003;98:23–47). Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

Cross-docking and milk run logistics in a consolidation network: A hybrid of harmony search and simulated annealing approach

In this paper, we develop a novel integer programming model for the transportation problem of a consolidation network where a set of vehicles are used to transport goods from suppliers to their corresponding customers via three transportation systems: direct shipment, shipment through cross-dock (indirect shipment) and milk run. Since the proposed problem formulation is NP-hard, we offer a hybrid of harmony search (HS) and simulated annealing (SA) based heuristics (HS-SA algorithm) in order to solve the problem. The objective of this problem is to minimize the total shipping cost in the network, so it is tried to reduce the number of required vehicles using an efficient vehicle routing strategy in the algorithm. Solving several numerical examples demonstrates that our solving approach performs much better than GAMS/CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for large size problem instances.     

A two phase variable neighborhood search for the multi-product inventory routing problem

We address a multi-product inventory routing problem and propose a two-phase Variable Neighborhood Search (VNS) metaheuristic to solve it. In the first phase, VNS is used to solve a capacitated vehicle routing problem at each period to find an initial solution without taking into account the inventory. In the second phase, we iteratively improve the initial solution while minimizing both the transportation and inventory costs. For this, we propose two different algorithms, a Variable Neighborhood Descent and a Variable Neighborhood Search. We present an heuristic and a Linear Programming formulation, which are applied after each local search move, to determine the amount of products to collect from each supplier at each period. During the exploration, we use priority rules for suppliers and vehicles, based on the current delivery schedule over the planning horizon. Computational results show the efficiency of the proposed two-phase approach.     

Variable neighborhood search for the p-median

Consider a set L of potential locations for p facilities and a set U of locations of given users. The p-median problem is to locate simultaneously the p facilities at locations of L in order to minimize the total transportation cost for satisfying the demand of the users, each supplied from its closest facility. This model is a basic one in location theory and can also be interpreted in terms of cluster analysis where locations of users are then replaced by points in a given space. We propose several new Variable Neighborhood Search heuristics for the p-median problem and compare them with Greedy plus Interchange, and two Tabu Search heuristics.     

New mixed integer approach to solve a multi-level capacitated disassembly lot-sizing problem with defective items and backlogging

The disassembly process has attracted mounting interest due to growing green concerns. This paper addresses the capacitated dynamic lot-sizing problem with external procurement, defective and backordered items, setup times, and extra capacity. The problem is to determine how many end-of-life products to disassemble during each period. We propose a new mixed-integer programming (MIP) approach to formulate the problem under study in order to maximize the disassembly-process gain, which is obtained as the difference between the revenue achieved by resale of the items recovered after disassembly and the costs tied to operating the disassembly tasks. Several numerical tests using the well-known CPLEX solver proved that this new model can find the optimal disassembly schedule for most test instances within an acceptable computational time. Furthermore, we led sensitivity studies on disassembly capacity, setup time and procurement cost. Test results validate the power of the suggested model and provide helpful insights for industry practitioners.     

VNS methods for home care routing and scheduling problem with temporal dependencies,and multiple structures and specialties

The need for optimization in the Home Care Service is becoming more and more legitimate in the face of the increase of demand and cost all over the world. Recently, many researchers in the Operation Research community have been attracted by this issue, which presents interesting aspects related to the vehicle routing problems. In this paper, we consider a new variant called the vehicle routing problem with time windows, temporal dependencies (synchronization, precedence, and disjunction), multi‐structures, and multispecialties problem (VRPTW‐TD‐2MS). This new variant is an extension of the vehicle routing problems with time windows and synchronization constraints (VRPTW‐S) that is well‐studied in literature. We present a Mixed Integer Programming method, and propose three Variable Neighborhood Search approaches. Extensive experiments show the effectiveness and efficiency of the General Variable Neighborhood Search with Ejection Chains‐based local search for solving VRPTW‐TD‐2MS and VRPTW‐S.     

A new approach to solve the multi-product multi-period inventory lot sizing with supplier selection problem

This research work deals with the multi-product multi-period inventory lot sizing with supplier selection problem. Formerly, this kind of problem was formulated and solved using an exhaustive enumeration algorithm and a heuristic algorithm. In this paper, a new algorithm based on a reduce and optimize approach and a new valid inequality is proposed to solve the multi-product multi-period inventory lot sizing with supplier selection problem. Numerical experiments ratify the success of the proposed heuristic algorithm. For the set of 150 benchmark instances, including 75 small-sized instances, 30 medium-sized instances, and 45 large-sized instances, the algorithm always obtained better solutions compared with those previously published. Furthermore, according to the computational results, the developed heuristic algorithm outperforms the CPLEX MIP solver in both solution quality and computational time.     

Competitive Liner Shipping Network Design

We present a solution method for the liner shipping network design problem which is a core strategic planning problem faced by container carriers. We propose the first practical algorithm which explicitly handles transshipment time limits for all demands. Individual sailing speeds at each service leg are used to balance sailing speed against operational costs, hence ensuring that the found network is competitive on both transit time and cost. We present a matheuristic for the problem where a MIP is used to select which ports should be inserted or removed on a route. Computational results are presented showing very promising results for realistic global liner shipping networks. Due to a number of algorithmic enhancements, the obtained solutions can be found within the same time frame as used by previous algorithms not handling time constraints. Furthermore, we present a sensitivity analysis on fluctuations in bunker price which confirms the applicability of the algorithm.