Bouzid, M. and Salhi, S. (2020). Packing rectangles into a fixed size circular container: Constructive and metaheuristic search approaches. European Journal of Operational Research [Online]. Available at: https://doi.org/10.1016/j.ejor.2020.02.048.
We investigate the orthogonal packing of rectangular objects into a circular container of fixed radius. We propose a new constructive heuristic called pack which builds a feasible packing starting from an ordered list of rectangles. This decoding procedure is polynomial and permits to move from the permutations search space to the packings search space by means of simple combinatorial moves combined with powerful geometrical analytical forms. The pack procedure is integrated into two well known metaheuristics, namely, a variable neighbourhood search (VNS) and a simulated annealing (SA). Two variants, namely xVNS and xSA, which stand as accelerated versions of VNS and SA are also presented. The proposed methodology produces 32 new best solutions out of the 54 benchmark instances while requiring less computational effort than the state-of-the-art method. In addition, we conduct experiments on newly generated larger instances which we have made publicly available alongside their respective results obtained from the proposed metaheuristics.
Moon, I., Salhi, S. and Feng, X. (2020). The location-routing problem with multi-compartment and multi-trip: formulation and heuristic approaches. Transportmetrica A: Transport Science [Online] 16:501-528. Available at: https://doi.org/10.1080/23249935.2020.1720036.
The location-routing problem with multi-compartment and multi-trip is an extension to the standard location-routing problem. In this problem, depots are used to deliver different products using heterogeneous vehicles with several compartments. Each compartment has a limited capacity and is dedicated to a single type of product. The problem is formulated as a mixed integer program. A constructive heuristic and a hybrid genetic algorithm (HGA) are proposed. Numerical experiments show that both heuristics can efficiently determine the optimal solutions on small size instances. For larger ones, the HGA outperforms the constructive heuristic with relatively more computational time. Managerial insights have been obtained from sensitivity analyses which would be helpful to improve the performance of the supply network.
Shahmanzari, M., Aksen, D. and Salhi, S. (2020). Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics. European Journal of Operational Research [Online] 280:656-670. Available at: https://dx.doi.org/10.1016/j.ejor.2019.07.035.
In this paper we investigate a novel logistical problem. The goal is to determine daily tours for a traveling salesperson who collects rewards from activities in cities during a fixed campaign period. We refer to this problem as the Roaming Salesman Problem (RSP) motivated by real-world applications including election logistics, touristic trip planning and marketing campaigns. RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP with static arc costs and time-dependent node rewards. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with city selection while the second phase focuses on route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities on a given day. The proposed matheuristic decomposes the RSP into as many subproblems as the number of campaign days. Computational results show that our approach provides near-optimal solutions in significantly shorter times compared to commercial solvers.
Irawan, C., Salhi, S. and Soemadi, K. (2020). The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods. Journal of Global Optimization [Online] 78:271-294. Available at: https://doi.org/10.1007/s10898-019-00862-2.
The continuous single-source capacitated multi-facility Weber problem (SSCMFWP) where setup cost of opening facilities is taken into account is investigated. The aim is to locate a set of facilities on the plane, to define their respective capacities which can be linked to the configuration of the processing machines used, and to allocate customers to exactly one facility with the objective being the minimisation of the total transportation and setup costs. A new nonlinear mathematical model based on the SSCMFWP is introduced where Rectilinear and Euclidean distances are used. Efficient metaheuristic approaches based on Variable Neighbourhood Search and Simulated Annealing are also developed. The proposed metaheuristics incorporate an exact method and the commonly used Cooper’s alternate location-allocation method. We also constructed a new data set to reflect the characteristic of this particular location problem as no data set is available in the literature. Computational experiments show that the proposed metaheuristics generate interesting results for this class of continuous location problems.
Wang, H., Yao, Y. and Salhi, S. (2020). Tension in big data using machine learning: Analysis and applications. Technological Forecasting and Social Change [Online] 158. Available at: https://doi.org/10.1016/j.techfore.2020.120175.
The access of machine learning techniques in popular programming languages and the exponentially expanding big data from social media, news, surveys, and markets provide exciting challenges and invaluable opportunities for organizations and individuals to explore implicit information for decision making. Nevertheless, the users of machine learning usually find that these sophisticated techniques could incur a high level of tensions caused by the selection of the appropriate size of the training data set among other factors. In this paper, we provide a systematic way of resolving such tensions by examining practical examples of predicting popularity and sentiment of posts on Twitter and Facebook, blogs on Mashable, news on Google and Yahoo, the US house survey, and Bitcoin prices. Interesting results show that for the case of big data, using around 20% of the full sample often leads to a better prediction accuracy than opting for the full sample. Our conclusion is found to be consistent across a series of experiments. The managerial implication is that using more is not necessarily the best and users need to be cautious about such an important sensitivity as the simplistic approach may easily lead to inferior solutions with potentially detrimental consequences.
Drezner, Z., Kalczynski, P. and Salhi, S. (2019). The planar multiple obnoxious facilities location problem: A Voronoi based heuristic. Omega [Online] 87:105-116. Available at: https://doi.org/10.1016/j.omega.2018.08.013.
Consider the situation where a given number of facilities are to be located in a convex polygon with the objective of maximizing the minimum distance between facilities and a given set of communities with the important additional condition that the facilities have to be farther than a certain distance from one another. This continuous multiple obnoxious facility location problem, which has two variants, is very complex to solve using commercial nonlinear optimizers. We propose a mathematical formulation and a heuristic approach based on Voronoi diagrams and an optimally solved binary linear program. As there are no nonlinear optimization solvers that guarantee optimality, we compare our results with a popular multi-start approach using interior point, genetic algorithm (GA), and sparse non-linear optimizer (SNOPT) solvers in Matlab. These are state of the art solvers for dealing with constrained non linear problems. Each instance is solved using 100 randomly generated starting solutions and the overall best is then selected. It was found that the proposed heuristic results are much better and were obtained in a fraction of the computer time required by the other methods.The multiple obnoxious location problem is a perfect example where all-purpose non-linear non-convex solvers perform poorly and hence the best way forward is to design and analyze heuristics that have the power and the exibility to deal with such a high level of complexity.
Irawan, C., Luis, M., Salhi, S. and Imran, A. (2019). The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem. Annals of Operations Research [Online] 275:367-392. Available at: https://doi.org/10.1007/s10479-018-3014-9.
In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.
Cruz, N., Salhi, S., Redondo, J., Álvarez, J., Berenguel, M. and Ortigosa, P. (2019). Design of a parallel genetic algorithm for continuous and pattern-free heliostat field optimization. The Journal of Supercomputing [Online] 75:1268-1283. Available at: https://doi.org/10.1007/s11227-018-2404-8.
The heliostat field of solar power tower plants can suppose up to 50% of investment costs and 40% of energy loss. Unfortunately, obtaining an optimal field requires facing a complex non-convex, continuous, large-scale, and constrained optimization problem. Although pattern-based layouts and iterative deployment are popular heuristics to simplify the problem, they limit flexibility and might be suboptimal. This work describes a new genetic algorithm for continuous and pattern-free heliostat field optimization. Considering the potential computational cost of the objective function and the necessity of broad explorations, it has been adapted to run in parallel on shared-memory environments. It relies on elitism, uniform crossover, static penalization of infeasibility, and tournament selection. Interesting experimental results show an optimization speedup up to 15× with 16 threads. It could approximately reduce a one year runtime, at complete optimization, to a month only. The optimizer has also been made available as a generic C++ library.
Callaghan, B., Salhi, S. and Brimberg, J. (2019). Optimal solutions for the continuous p-centre problem and related α-neighbour and conditional problems: A relaxation-based algorithm. Journal of the Operational Research Society [Online] 70:192-211. Available at: https://doi.org/10.1080/01605682.2017.1421854.
This paper aims to solve large continuous p-centre problems optimally by re-examining a recent relaxation-based algorithm. The algorithm is strengthened by adding four mathematically supported enhancements to improve its efficiency. This revised relaxation algorithm yields a massive reduction in computational time enabling for the first time larger data-sets to be solved optimally (e.g., up to 1323 nodes). The enhanced algorithm is also shown to be flexible as it can be easily adapted to optimally solve related practical location problems that are frequently faced by senior management when making strategic decisions. These include the α-neighbour p-centre problem and the conditional p-centre problem. A scenario analysis using variable α is also performed to provide further managerial insights.
Salhi, S., Eglese, R. and Hadjiconstantinou, E. (2019). Preface: advances in theoretical and practical combinatorial optimization. Annals of Operations Research [Online] 272:1-2. Available at: https://doi.org/10.1007/s10479-018-3072-z.
Mohamed, N., Salhi, S., Nagy, G. and Mohamed, N. (2019). A Matheuristic Approach for the Split Delivery Vehicle Routing Problem: An Efficient Set Covering-Based Model with Guided Route Generation Schemes. International Journal of Mathematics in Operational Research [Online] 15:65-91. Available at: http://dx.doi.org/10.1504/IJMOR.2019.10022832.
The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxed version of the classical VRP where customers can be visited more than once. The SDVRP is also applicable for problems where one or more of the customers require a demand larger than the vehicle capacity. Constructive heuristics adapted from the parallel savings and the sweep methods are first proposed to generate a set of solutions which is then used in the new and more efficient set covering-based formulation which we put forward. An effective repair mechanism to remedy any infeasibility due to the set covering problem is presented. A reduced set of promising routes is used in our model, instead of the original set of routes, proposing and using well defined reduction schemes. This set covering-based approach is tested on large data sets from the literature with encouraging results. In brief, 7 best solutions including ties are found among the 137 SDVRP instances.
Simeonova, L., Wassan, N., Salhi, S. and Nagy, G. (2018). The heterogeneous fleet vehicle routing problem with light loads and overtime: Formulation and population variable neighbourhood search with adaptive memory. Expert Systems with Applications [Online] 114:183-195. Available at: https://dx.doi.org/10.1016/j.eswa.2018.07.034.
In this paper we consider a real life Vehicle Routing Problem inspired by the gas delivery industry in the United Kingdom. The problem is characterized by heterogeneous vehicle fleet, demand-dependent service times, maximum allowable overtime and a special light load requirement. A mathematical formulation of the problem is developed and optimal solutions for small sized instances are found. A new learning-based Population Variable Neighbourhood Search algorithm is designed to address this real life logistic problem. To the best of our knowledge Adaptive Memory has not been hybridized with a classical iterative memoryless method. In this paper we devise and analyse empirically a new and effective hybridization search that considers both memory extraction and exploitation. In terms of practical implications, we show that on a daily basis up to 8% cost savings on average can be achieved when overtime and light load requirements are considered in the decision making process. Moreover, accommodating for allowable overtime has shown to yield 12% better average utilization of the driver's working hours and 12.5% better average utilization of the vehicle load, without a significant increase in running costs. We also further discuss some managerial insights and trade-offs.
Cruz, N., Salhi, S., Redondo, J., Álvarez, J., Berenguel, M. and Ortigosa, P. (2018). Hector, a new methodology for continuous and pattern-free heliostat field optimization. Applied Energy [Online] 225:1123-1131. Available at: https://doi.org/10.1016/j.apenergy.2018.05.072.
In the framework of central receiver solar plants, the heliostat field can take up to 50% of the initial investment and cause up to 40% of energy loss. The most popular design strategies are based on: (i) forcing heliostats to follow known distribution patterns and (ii) iterative selection of positions. However, these methods might produce suboptimal solutions. The evolution of computational platforms allows the development of more flexible approaches. In this work, Hector, a new meta-heuristic aimed at facilitating coordinate-based optimization, is presented. First, since East-West symmetry is imposed, one of those regions is ignored and the number of heliostats to be placed is halved. Second, the selected region is split into separate circular sectors around the receiver. Next, at every iteration, a new heliostat is added to the most promising sector. Then, it is optimized by a user-selected algorithm, as an independent problem, in a continuous search-space. This procedure is repeated until all the required heliostats have been deployed. The computed half is finally cloned into the other one. Two versions of this strategy are proposed. Our empirical results show that, for a given optimizer, better fields are obtained with Hector. The second version yields the best fields but requires more runtime.
Drezner, Z. and Salhi, S. (2017). Incorporating Neighborhood Reduction for the Solution of the Planar p-Median Problem. Annals of Operations Research [Online] 258:639-654. Available at: http://dx.doi.org/10.1007/s10479-015-1961-y.
Two efficient neighbourhood reduction schemes are proposed for the solution of the p-Median problem
on the plane. Their integration into a local search significantly reduces the run time with an insignificant
deterioration in the quality of the solution. For completeness this fast local search is also embedded
into one of the most powerful meta-heuristic algorithms recently developed for this continuous location
problem. Excellent results for instances with up to 1060 demand points with various values of p are
reported. Eight new best known solutions for ten instances of a large problem with 3,038 demand points
and up to 500 facilities are also found.
Sze, J., Salhi, S. and Wassan, N. (2017). The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search. Transportation Research Part B: Methodological [Online] 101:162-184. Available at: http://dx.doi.org/10.1016/j.trb.2017.04.003.
The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new variant of the classical capacitated vehicle routing problem in which the objective is to minimise the sum of arrival times at customers (min-sum) instead of the total route distance. While the literature for the CCVRP is scarce, this problem has useful applications especially in the area of supplying humanitarian aid after a natural disaster. In this paper, a two-stage adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed. When tested on the benchmark data sets, the results show that the proposed AVNS is highly competitive in producing new best known solutions to more than half of the instances. An alternative but related objective that minimises the maximum arrival time (min-max) is also explored in this study demonstrating the flexibility and the effectiveness of the proposed metaheuristic. To the best of our knowledge, this is the first study that exploits the min-max objective of the CCVRP in addition to providing extensive computational results for a large number of instances for the min-sum. As a by-product of this study, managerial insights for decision making are also presented.
Irawana, C., Salhi, S., Luis, M. and Azizi, N. (2017). The continuous single source location problem with capacity and zone-dependent fixed cost: Models and solution approaches. European Journal of Operational Research [Online] 263:94-107. Available at: https://dx.doi.org/10.1016/j.ejor.2017.04.004.
The continuous capacitated single-source multi-facility Weber problem with the presence of facility fixed cost is investigated. A new mathematical model which incorporates multi-level type capacity (or design) and facility fixed cost that is capacity-based and zone-dependent is introduced. As no data set exists for this new location problem, a new data set based on convex polygons using triangular shape is constructed. A generalised two stage heuristic scheme that combines the concept of aggregation, an exact method, and an enhanced Cooper’s alternate location-allocation method is put forward. A framework that embeds Variable Neighbourhood Search is also proposed. Computational experiments show that these matheuristics produce encouraging results for this class of location problems. The proposed approaches are also easily adapted to cater for a recently studied variant namely the single-source capacitated multi-facility Weber problem where they outperform those recently published solution methods
Callaghan, B., Salhi, S. and Nagy, G. (2017). Speeding up the optimal method of Drezner for the p-centre problem in the plane. European Journal of Operational Research [Online] 257:722-734. Available at: http://dx.doi.org/10.1016/j.ejor.2016.08.038.
This paper revisits an early but interesting optimal algorithm first proposed by Drezner to solve the continuous p-centre problem. The original algorithm is reexamined and efficient neighbourhood reductions which are mathematically supported are proposed to improve its overall computational performance. The revised algorithm yields a considerably high reduction in computational time reaching, in some cases, a decrease of 96%. This new algorithm is now able to find proven optimal solutions for large data sets with over 1300 demand points and various values of p for the first time.
Bouzid, M., Ait Haddadene, H. and Salhi, S. (2017). An Integration of Lagrangian Split and VNS: The case of the Capacitated Vehicle Routing Problem. Computers and Operations Research [Online] 78:513-525. Available at: http://dx.doi.org/10.1016/j.cor.2016.02.009.
In this paper, we propose an efficient and novel Lagrangian relaxation method which incorporates a new integer linear programming (ILP) formulation to optimally partition a giant tour in the context of a capacitated vehicle routing problem (CVRP). This approach, which we call Lagrangian split (Ls), is more versatile than the ILP which, in most cases, can be intractable using a conventional solver. An effective repair mechanism followed by a local search are also embedded into the process. The mathematical validity of the repair mechanism and its time complexity are also provided. An integration of Ls into a powerful variable neighbourhood search (VNS) is also presented. Computational experiments are conducted to demonstrate that Ls provides encouraging results when applied on benchmark instances and that the integration of Ls into a metaheuristic scheme produces good results when compared to those found by state-of-the-art methods.
Wassan, N., Wassan, N., Nagy, G. and Salhi, S. (2017). The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighbourhood Search. Computers & Operations Research [Online] 78:454-467. Available at: http://dx.doi.org/10.1016/j.cor.2015.12.017.
In this paper a new VRP variant the Multiple Trip Vehicle Routing Problem with Backhauls (MT-VRPB) is investigated. The classical MT-VRP model is extended by including the backhauling aspect. An ILP formulation of the MT-VRPB is first presented and CPLEX results for small and medium size instances are reported. For large instances of the MT-VRPB a Two-Level VNS algorithm is developed. To gain a continuous balanced intensification and diversification during the search process VNS is embedded with the sequential VND and a multi-layer local search approach. The algorithm is tested on a set of new MT-VRPB data instances which we generated. Interesting computational results are presented. The Two-Level VNS produced excellent results when tested on the special variant of the VRPB.
Brimberg, J., Drezner, Z., Mladenovic, N. and Salhi, S. (2017). Using injection points in reformulation local search for solving continuous location problems. Yugoslav Journal of Operations Research [Online] 27:291-300. Available at: https://doi.org/10.2298/YJOR160517018B.
Reformulation local search (RLS) has been recently proposed as a new approach for solving continuous location problems. The main idea, although not new, is to exploit the relation between the continuous model and its discrete counterpart. The RLS switches between the continuous model and a discrete relaxation in order to expand the search. In each iteration new points obtained in the continuous phase are added to the discrete formulation. Thus, the two formulations become equivalent in a limiting sense. In this paper we introduce the idea of adding 'injection points' in the discrete phase of RLS in order to escape a current local solution. Preliminary results are obtained on benchmark data sets for the multi-source Weber problem that support further investigation of the RLS framework.
Acquaye, A., Feng, K., Oppon, E., Salhi, S., Ibn-Mohammed, T., Genovese, A. and Hubacek, K. (2016). Measuring the Environmental Sustainability Performance of Global Supply Chains: a Multi-Regional Input-Output analysis for Carbon, Sulphur Oxide and Water Footprints. Journal of Environmental Management [Online] 187:571-585. Available at: http://dx.doi.org/10.1016/j.jenvman.2016.10.059.
Measuring the performance of what an environmentally sustainable supply chain has become a challenge despite the convergence of the underlining principles of sustainable supply chain management. This challenge is exacerbated by the fact that supply chains are inherently dynamic and complex and also because multiple measures can be used to characterize performances.
By identifying some of the critical issues in the literature regarding performance measurements, this paper contributes to the existing body of literature by adopting an environmental performance measurement approach for economic sectors (primary, secondary and tertiary sectors). It uses economic sectors and evaluates them on a sectoral level in specific countries as well as part of the Global Value Chain based on the established multi-regional input-output (MRIO) modelling framework. The MRIO model has been used to calculate direct and indirect (that is supply chain or upstream) environmental effects such as CO2, SO2, biodiversity, water consumption and pollution to name just a few of the applications. In this paper we use MRIO to calculate emissions and resource consumption intensities and footprints, direct and indirect impacts, and net emission flows between countries. These are exemplified by using carbon emissions, sulphur oxide emissions and water use in two highly polluting industries; Electricity production and Chemical industry in 33 countries, including the EU-27, Brazil, India and China, the USA, Canada and Japan from 1995 to 2009. Some of the results highlights include: On average, direct carbon emissions in the electricity sector across all 27 member states of the EU was estimated to be 1368 million tonnes and indirect carbon emissions to be 470.7 million tonnes per year representing 25.6% of the EU-27 total carbon emissions related to this sector. It was also observed that from 2004, sulphur oxide emissions intensities in electricity production in India and China have remained relatively constant at about 62.8 gSOx/$ and 84.4 gSOx/$ although being higher than in other countries. In terms of water use, the high water use intensity in China (1040.27 litres/$) and India (961.63 litres/$), which are among the highest in the sector in the electricity sector is exacerbated by both countries being ranked as High Water Stress Risk countries.
The paper also highlights many merits of the MRIO including: a 15-year time series study (which provides a measurement of environmental performance of key industries and an opportunity to assess technical and technological change during the investigated time period), a supply chain approach that provides a consistent methodological framework and accounts for all upstream supply chain environmental impacts throughout entire global supply chains.
The paper also discusses the implications of the study to environmental sustainability performance measurement in terms of the level of analysis from a value chain hierarchy perspective, methodological issues, performance indicators, environmental exchanges and policy relevance.
Sze, J., Salhi, S. and Wassan, N. (2016). A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem. Expert Systems with Applications [Online] 65:383-397. Available at: https://doi.org/10.1016/j.eswa.2016.08.060.
In this paper, an adaptive variable neighbourhood search (AVNS) algorithm that
incorporates large neighbourhood search (LNS) as a diversification strategy is proposed
and applied to the capacitated vehicle routing problem. The AVNS consists
of two stages: a learning phase and a multi-level VNS with guided local search.
The adaptive aspect is integrated in the local search where a set of highly successful
local searches is selected based on the intelligent selection mechanism. In
addition, the hybridisation of LNS with the AVNS enables the solution to escape
from the local minimum effectively. To make the algorithm more competitive in
terms of the computing time, a simple and flexible data structure and a neighbourhood
reduction scheme are embedded. Finally, we adapt a new local search move
and an effective removal strategy for the LNS. The proposed AVNS was tested
on the benchmark data sets from the literature and produced very competitive
Elshaikh, A., Salhi, S., Brimberg, J., Mladenovic, N., Callaghan, B. and Nagy, G. (2016). An Adaptive Perturbation-Based Heuristic: An Application to the Continuous p-Centre Problem. Computers and Operations Research [Online] 75:1-11. Available at: http://www.dx.doi.org/10.1016/j.cor.2016.04.018.
A self-adaptive heuristic that incorporates a variable level of perturbation, a novel local search and a learning mechanism is proposed to solve the p-centre problem in the continuous space. Empirical results, using several large TSP-Lib data sets, some with over 1300 customers with various values of p, show that our proposed heuristic is both effective and efficient. This perturbation metaheuristic compares favourably against the optimal method on small size instances. For larger instances the algorithm outperforms both a multi-start heuristic and a discrete-based optimal approach while performing well against a recent powerful VNS approach. This is a self-adaptive method that can easily be adopted to tackle other combinatorial/global optimisation problems. For benchmarking purposes, the medium size instances with nodes are solved optimally for the first time, though requiring a large amount of computational time. As a by-product of this research, we also report for the first time the optimal solution of the vertex p-centre problem for these TSP-Lib data sets.
Azizi, N., Chauhan, S., Salhi, S. and Vidyarthi, N. (2016). The impact of hub failure in Hub-and-Spoke networks: Mathematical formulations and solution techniques. Computers & Operations Research 65:174-188.
Hub facilities are subject to unpredictable disruptions caused by severe weather condition, natural disasters, labour dispute, and vandalism to cite a few. Disruptions at hubs result in excessive transportation costs and economic losses as customers (demand) initially served by these facilities must now be served by other hubs. In this study, we first present a novel mathematical model that builds hub-and-spoke systems under the risk of hub disruption. In developing the model, we assume that once a hub stops normal operations, the entire demand initially served by this hub is handled by a backup facility. The objective function of the model minimizes the weighted sum of transportation cost in regular situation and the expected transportation cost following hub failure. We adopted a linearization for the model and present an efficient evolutionary approach with specifically designed operators. We solved a number of small problem instances from the literature using CPLEX for our enhanced mathematical model. The obtained results are also used as a platform for assessing the performance of our proposed meta-heuristic which is then tested on large instances with promising results. We further study and provide results for the relaxed problem in which demand points affected by disruption are allowed to be reallocated to any of the operational hubs in the network.
Irawan, C., Salhi, S. and Drezner, Z. (2016). Hybrid Meta-heuristics with VNS and Exact Methods: Application to Large Unconditional and Conditional Vertex p-Centre Problems. Journal of Heuristics [Online] 22:507-537. Available at: http://dx.doi.org/10.1007/s10732-014-9277-7.
Large-scale unconditional and conditional vertex p-centre problems are solved using two meta-heuristics. One is based on a three-stage approach whereas the other relies on a guided multi-start principle. Both methods incorporate Variable Neighbourhood Search, exact method, and aggregation techniques. The methods are assessed on the TSP dataset which consist of up to 71,009 demand points with p varying from 5 to 100. To the best of our knowledge, these are the largest instances solved for unconditional and conditional vertex p-centre problems. The two proposed meta-heuristics yield competitive results for both classes of problems.
Mohamed, N., Zainuddin, Z., Salhi, S. and Mohamed, N. (2016). The Integrated Aircraft Routing and Crew Pairing Problem: ILP Based Formulations. Jurnal Teknologi [Online] 78:79-85. Available at: http://www.jurnalteknologi.utm.my/index.php/jurnalteknologi/article/view/9004.
Minimization of cost is very important in airline as great profit is an important objective for
any airline system. One way to minimize the costs in airline is by developing an integrated
planning process. Airline planning consists of many difficult operational decision problems
including aircraft routing and crew pairing problems. These two sub-problems, though
interrelated in practice, are usually solved sequentially leading to suboptimal solutions. We
propose an integrated aircraft routing and crew pairing problem model, one approach to
generate the feasible aircraft routes and crew pairs, followed by three approaches to
solve the integrated model. The integrated aircraft routing and crew scheduling problem
is to determine a minimum cost aircraft routes and crew schedules while each flight leg is
covered by one aircraft and one crew. The first approach is an integer programming
solution method, the second formulation is developed in a way to lend itself to be used
efficiently by Dantzig Wolfe decomposition whereas the third one is formulated as a
Benders decomposition method. Encouraging results are obtained when tested on four
types of aircraft based on local flights in Malaysia for one week flight cycle.
Salhi, S., Drezner, Z., Brimberg, J. and Mladenovic, N. (2015). Solving the planar p-median problem by variable neighborhood and concentric searches. Journal of Global Optimization [Online] 63:501-514. Available at: http://dx.doi.org/10.1007/s10898-014-0183-1.
Two new approaches for the solution of the p-median problem
in the plane are proposed. One is a Variable Neighborhood Search (VNS)
and the other one is a concentric search. Both approaches are enhanced by a
front-end procedure for finding good starting solutions and a decomposition
heuristic acting as a post optimization procedure. Computational results
confirm the effectiveness of the proposed algorithms.
Drezner, Z., Brimberg, J., Mladenovic, N. and Salhi, S. (2015). New heuristic algorithms for solving the planar p-median problem. Computers and Operations Research [Online] 62:296-304. Available at: http://dx.doi.org/10.1016/j.cor.2014.05.010.
In this paper we propose effective heuristics for the solution of the planar p-median problem.
We develop a new distribution based variable neighborhood search and a new genetic algorithm,
and also test a hybrid algorithm that combines these two approaches. The best results were
obtained by the hybrid approach. The best known solution was found in 466 out of 470 runs,
and the average solution was only 0.000016% above the best known solution on 47 well explored
test instances of 654 and 1060 demand points and up to 150 facilities.
Shaikh, A., Salhi, S. and Ndiaye, M. (2015). New MAXCAP Related Problems: Formulation and Model Solutions: A class of competitive location problems. Computers & Industrial Engineering [Online] 85:248-259. Available at: http://dx.doi.org/10.1016/j.cie.2015.03.018.
In this paper three related problems of the maximum capture (MAXCAP) model are proposed. These include the case where facilities provide a certain amount of service level for the customers, the possibility where customers do not allocate their demand completely to one facility but prorate their demand based on the service level, and finally we explore the situation where customers will not opt for sharing their demand irrespective of the service level if the next attractive facility is too far way which we express by a distance threshold. These models are put forward to mimic realistic situations related to customer behaviour when it comes to selecting a facility. Their respective mathematical formulations are put forward and tested on a case study and also over a range of larger data sets.
Irawan, C. and Salhi, S. (2015). Solving Large p-median Problems by a Multistage Hybrid Approach Using Demand Points Aggregation and Variable Neighbourhood Search. Journal of Global Optimization [Online] 63:537-554. Available at: http://dx.doi.org/10.1007/s10898-013-0080-z.
A hybridisation of a clustering-based technique and of a variable neighbourhood
search (VNS) is designed to solve large-scale p-median problems. The approach is based
on a multi-stage methodology where learning from previous stages is taken into account
when tackling the next stage. Each stage is made up of several subproblems that are solved
by a fast procedure to produce good feasible solutions. Within each stage, the solutions
returned are put together to make up a new promising subset of potential facilities. This
augmented p-median problem is then solved by VNS. As these problems used aggregation,
a cost evaluation based on the original demand points instead of aggregation is computed
for each of the ‘aggregation’-based solution. The one yielding the least cost is then selected
and its chosen facilities included into the next stages. This multi-stage process is repeated
several times until a certain criterion is met. This approach is enhanced by an efficient way
to aggregate the data and a neighbourhood reduction scheme when allocating demand points
to their nearest facilities. The proposed approach is tested, using various values of p, on
the largest data sets from the literature with up to 89,600 demand points with encouraging
Luis, M., Salhi, S. and Nagy, G. (2015). A Constructive Method and a Guided Hybrid GRASP for the Capacitated Multi-source Weber Problem in the Presence of Fixed Cost. Journal of Algorithms & Computational Technology [Online] 9:215-232. Available at: http://dx.doi.org/10.1260/1748-3018.9.2.215.
This paper presents a new variant of the capacitated multi-source Weber problem that introduces fixed costs for opening facilities. Three types of fixed costs are considered and experimented upon. A guided constructive heuristic scheme based on the concept of restricted regions and a greedy randomized adaptive search procedure (GRASP) are proposed. The four known data sets in the literature, typically used for the uncapacitated multi-source Weber problem, are adapted by adding capacities and facility fixed costs and used as a platform to assess the performance of our proposed approaches. Computational results are provided and some research avenues highlighted.
Hosseininezhad, S., Salhi, S. and Jabalameli, M. (2015). A Cross Entropy-Based Heuristic for the Capacitated Multi-Source Weber Problem with Facility Fixed Cost: Cross entropy for continuous location problems. Computers & Industrial Engineering [Online] 83:151-158. Available at: http://dx.doi.org/10.1016/j.cie.2015.01.013.
This paper investigates a capacitated planar location-allocation problem with facility fixed cost. A zone-based fixed cost which consists of production and installation costs is considered. A nonlinear and mixed integer formulation is first presented. A powerful three stage Cross Entropy meta-heuristic with novel density functions is proposed. In the first stage a covering location problem providing a multivariate normal density function for the associated stochastic problem is solved. The allocation values considering a multinomial density function are obtained in the second stage. In the third stage, single facility continuous location problems are solved. Several instances of various sizes are used to assess the performance of the proposed meta-heuristic. Our approach performs well when compared with the optimizer GAMS which is used to provide the optimal solution for small size instances and lower/upper bounds for some of the larger ones.
Salhi, S. (2019). Variable Neighbourhood Search: 6th International Conference, ICVNS 2018, Sithonia, Greece, October 4–7, 2018, Revised Selected Papers. [Online]. Vol. 11328. Sifaleras, A., Salhi, S. and Brimberg, J. eds. Cham, Switzerland: Springer. Available at: http://dx.doi.org/10.1007/978-3-030-15843-9.
This book constitutes the refereed post-conference proceedings of the 6th International Conference on Variable Neighborhood Search, ICVNS 2018, held in Sithonia, Greece, in October 2018.
ICVNS 2018 received 49 submissions of which 23 full papers were carefully reviewed and selected.
VNS is a metaheuristic based on systematic changes in the neighborhood structure within a search for solving optimization problems and related tasks. The main goal of ICVNS 2018 was to provide a stimulating environment in which researchers coming from various scientific fields could share and discuss their knowledge, expertise, and ideas related to the VNS metaheuristic and its applications.
Salhi, S. (2019). Decision Science in Action: Theory and Applications of Modern Decision Analytic Optimisation. [Online]. Deep, K., Jain, M. and Salhi, S. eds. Singapore: Springer. Available at: http://dx.doi.org/10.1007/978-981-13-0860-4.
This book provides essential insights into a range of newly developed numerical optimization techniques with a view to solving real-world problems. Many of these problems can be modeled as nonlinear optimization problems, but due to their complex nature, it is not always possible to solve them using conventional optimization theory. Accordingly, the book discusses the design and applications of non-conventional numerical optimization techniques, including the design of benchmark functions and the implementation of these techniques to solve real-world optimization problems.
The book’s twenty chapters examine various interesting research topics in this area, including: Pi fraction-based optimization of the Pantoja–Bretones–Martin (PBM) antenna benchmarks; benchmark function generators for single-objective robust optimization algorithms; convergence of gravitational search algorithms on linear and quadratic functions; and an algorithm for the multi-variant evolutionary synthesis of nonlinear models with real-valued chromosomes.
Delivering on its promise to explore real-world scenarios, the book also addresses the seismic analysis of a multi-story building with optimized damper properties; the application of constrained spider monkey optimization to solve portfolio optimization problems; the effect of upper body motion on a bipedal robot’s stability; an ant colony algorithm for routing alternate-fuel vehicles in multi-depot vehicle routing problems; enhanced fractal dimension-based feature extraction for thermal face recognition; and an artificial bee colony-based hyper-heuristic for the single machine order acceptance and scheduling problem.
The book will benefit not only researchers, but also organizations active in such varied fields as Aerospace, Automotive, Biotechnology, Consumer Packaged Goods, Electronics, Finance, Business & Banking, Oil, Gas & Geosciences, and Pharma, to name a few.
Salhi, S. (2019). Logistics, Supply Chain and Financial Predictive Analytics: Theory and Practice. [Online]. Deep, K., Jain, M. and Salhi, S. eds. Singapore: Springer, Singapore. Available at: http://dx.doi.org/10.1007/978-981-13-0872-7.
This book addresses a broad range of problems commonly encountered in the fields of
financial analysis, logistics and supply chain management, such as the use of big data analytics
in the banking sector. Divided into twenty chapters, some of the contemporary topics discussed
in the book are co-operative/non-cooperative supply chain models for imperfect quality items
with trade-credit financing; a non-dominated sorting water cycle algorithm for the cardinality
constrained portfolio problem; and determining initial, basic and feasible solutions for
transportation problems by means of the “supply demand reparation method” and “continuous
allocation method.” In addition, the book delves into a comparison study on exponential
smoothing and the Arima model for fuel prices; optimal policy for Weibull distributed
deteriorating items varying with ramp type demand rate and shortages; an inventory model
with shortages and deterioration for three different demand rates; outlier labeling methods for
medical data; a garbage disposal plant as a validated model of a fault-tolerant system; and
the design of a “least cost ration formulation application for cattle”; a preservation technology
model for deteriorating items with advertisement dependent demand and trade credit; a time
series model for stock price forecasting in India; and asset pricing using capital market curves.
The book offers a valuable asset for all researchers and industry practitioners working in these
areas, giving them a feel for the latest developments and encouraging them to pursue further
research in this direction.
Salhi, S. (2019). Performance Prediction and Analytics of Fuzzy, Reliability and Queuing Models : Theory and Applications. [Online]. Deep, K., Jain, M. and Salhi, S. eds. Singapore: Springer, Singapore. Available at: http://dx.doi.org/10.1007/978-981-13-0857-4.
This book presents the latest developments and breakthroughs in fuzzy theory and
performance prediction of queuing and reliability models by using the stochastic modeling and
optimization theory. The main focus is on analytics that use fuzzy logic, queuing and reliability
theory for the performance prediction and optimal design of real-time engineering systems
including call centers, telecommunication, manufacturing, service organizations, etc. For the dayto-
day as well as industrial queuing situations and reliability prediction of machining parts
embedded in computer, communication and manufacturing systems, the book assesses various
measures of performance and effectiveness that can provide valuable insights and help arrive
at the best decisions with regard to service and engineering systems. In twenty chapters, the
book presents both theoretical developments and applications of the fuzzy logic, reliability and
queuing models in a diverse range of scenarios. The topics discussed will be of interest to
researchers, educators and undergraduate students in the fields of Engineering, Business
Management, and the Mathematical Sciences.
Salhi, S. (2019). Advances in Theoretical and Practical Combinatorial Optimzation. [Online]. Vol. 272. Salhi, S., Eglese, R. and Hadjiconstantinou, E. eds. USA: Springer. Available at: https://dx.doi.org/10.1007/s10479-018-3072-z.
Preface: Advances in Theoretical and Practical Combinatorial Optimization
Said Salhi1, Richard Eglese2, Eleni Hadjiconstantinou3
This issue consists of research papers dedicated, though not limited, to the International Symposium in Combinatorial Optimisation (CO2016), chaired by Said Salhi and held at the University of Kent, Canterbury, 1-3 September 2016. Of the many good papers it attracted, 35 were considered suitable for the next stage of review, resulting in 20 being accepted mostly after two rounds of reviews. We divided the issue into three parts, each covering a wider though well-defined area within combinatorial optimization (CO). These three parts, which are not completely distinct, are referred to for simplicity as Mathematically-Oriented (MO), Heuristically-Based (HB) and Practically-Focussed (PF).
MO contains seven papers. These include a paper on the integration of network flows in a coloring algorithm by Koster, Scheidweiler, and Tieves; one on a polynomial time algorithm for the minimum flow problem by Khodayifar, Raayatpanah, and Pardalos, and one on a formulation in multi-level capacitated facility location by Irawan and Jones. A.Salhi, Alsoufi, and Yang provide a mixed integer program combined with an evolutionary approach for seaside operations in container ports, while Zare, Borrero, Zeng and Prokopyev have contributed a note on new linearized formulations in bilevel linear integer problems. Fuzzy logic is explored for portfolio optimization by Liagkouras and Metaxiotis, and for supplier selection by Chang.
HB covers six papers. Azizi, using a genetic algorithm, explores hub and spoke networks under disruption. Knust and Xie produce a simulated annealing algorithm for nurse rostering, while Pei, Cheng, Liu, Pardalos, and Kong investigate Variable Neighbourhood Search (VNS) for single and parallel machine serial batching. A skewed VNS is adopted by Derbel, Jarbaoui, and Bhiri for the heterogeneous fleet vehicle routing problem, and an ascent-escent VNS for the detection of community (cluster) structures in a network is discussed by Džamić, Aloise, and Mladenović. The last paper in this category is by Brimberg, Mladenović, Todosijević, and Urošević, who investigate the capacitated clustering problem using a variant of VNS.
PF has seven papers that treat inspiring implementations of CO for real-life applications. For example, in the area of scheduling, the use of spare parts in vessel maintenance is dealt with by Kian, Bektaş, and Ouelhadj, while shift scheduling for power station staff is explored by Shuib and Kamarudin. The avoidance of obstacles in off shore wind farms is optimized by Klein and Haugland, and the costing of a product within a supply chain is performed by de Matta. In the health area, the maximization of the expected number of kidney transplants is performed by Alvelos, Klimentova, and Viana; a preventive health care network is designed by Davari; and the layout of an operating theater is produced by Chraibi, Osman, and Kharraja.
Finally, we are grateful to Professor E. Boros for trusting our academic judgment in acting as guest editors of the Annals of Operations Research special issue devoted, but not restricted, to CO2016. We are also thankful to the managing editor, Katie D’Agosta, for her patience and valuable support in preparing this special issue.
1 Centre for Logistics and Heuristic Optimisation, Kent Business School, University of Kent, Canterbury, UK
2 Lancaster University Management School, Lancaster, UK
3 School of Business and Law, Frederick University Cyprus, Cyprus.
Sze, J. (2017). Hybridisation Search for A Class of Vehicle Routing Problems.
This thesis presents an investigation into the hybridisation of metaheuristic approaches to tackle the classical vehicle routing problem (VRP) and its adaptation to other useful and practical routing problems including the cumulative capacitated VRP (CCVRP) and the dynamic VRP (DVRP). Due to the limited success of the exact methods in handling large size instances, this research investigates the design and analysis of metaheuristic algorithms that can produce near optimal solutions within a reasonable amount of time to solve this class of routing problems. To achieve this goal, we propose an effective and novel hybridisation of variable neighbourhood search (VNS) and large neighbourhood search (LNS), leading to a powerful adaptive VNS (AVNS). Different from most of the literature for AVNS and adaptive LNS where learning is usually incorporated in the shaking step for the former and in the selection of the removal strategies for the latter, the adaptive aspect presented here is integrated in the local search of our AVNS. In short, a set of highly successful local searches is selected based on the intelligent selection mechanism which we introduced. In addition, this work also focuses on the development of some general enhancement-based techniques which include the design of neighbourhood reduction scheme, efficient data structures and a guided penalized objective function.
The VRP is a hard combinatorial optimisation problem which was first established more than fifty years ago. Since then, this problem is extensively studied because of its high practicability in transportation logistics. Given the rising price of global oil, reducing the transportation cost provides a great impact in stabilizing the global economic system and adds a competitive advantage. The classical VRP focuses on this line of research. In addition, the classical VRP is used as the initial platform for our experiments which serves as the basis for tackling the other related routing problems mentioned above. The aim is to turn the successful implementations of the proposed algorithm by easily adapting and extending it to cater for the other two related routing problems namely the CCVRP and the DVRP.
While the general assumption in most VRPs is profit-based such as the minimisation of the transportation cost, there are other objective functions such as to provide a good service to the customers. Such applications appear in the context of humanitarian relief where the main objective is to save lives or to alleviate suffering. This leads to the introduction of the CCVRP, which aims to minimise the sum of arrival times at customers. The literature for this particular problem is relatively scarce despite its practical importance. We therefore intend to investigate this new and interesting variant. In addition, during the emergency situation, there is often a limited time for saving lives. A good routing plan should also ensure fairness and equity to everyone including the last customer. Motivated by this idea, an alternative but closely related objective that minimises the last arrival time is also studied. We refer to this variant as the min-max CCVRP.
In the traditional VRP, a route plan remains unchanged once it is identified. However in practice, several unforeseen events such as accidents or bad weather could occur at any point when the routes are executed, which cause traffic congestion and delay to the original planned routes. Therefore, it is important to re-optimise the routes by taking into consideration the real-time information, leading to the DVRP. The review of the DVRP literature shows that researchers have mainly focused on the customer requests as the dynamic aspect. Our research, however, concentrates more on the less popular but very practical aspect, namely the dynamic traffic information. Such unpredictable events have a great impact on the route plan and henceforth shall, in overview, not be ignored.
The contributions of this thesis are fourfold: (i) To propose an effective hybridisation of the VNS and the LNS in addition to some new and powerful data structures and neighbourhood reduction scheme integrated in the algorithm, (ii) To adapt the AVNS algorithm for the CCVRP with extra features added and to present new best results, (iii) To demonstrate the flexibility and effectiveness of the AVNS algorithm to solve the min-max CCVRP and to explore the managerial insights for decision making when considering the min-sum and the min-max CCVRP objective functions, (iv) To adapt the AVNS algorithm as a re-optimisation procedure for the DVRP, where we introduce the concept of critical points which are used as the turning points for the vehicle.
Callaghan, R. (2016). An Investigation into Exact Methods for the Continuous p?Centre Problem and Its Related Problems.
This thesis will analyse, investigate and develop new and interesting ideas to optimally solve a location problem called the continuous p?centre problem. This problem wishes to locate p facilities in a plane or network of n demand points such that the maximum distance or travel time between each demand point and its closest facility is minimised. Several difficulties are identified which are to be overcome to solve the continuous p?centre problem optimally. These relate to producing a finite set of potential facility locations or decreasing the problem size so that less computational time and effort is required. This thesis will examine several schemes that can be applied to this location problem and its related version with the aim to optimally solve large problems that were previously unsolved.
This thesis contains eight chapters. The first three chapters provide an introduction into location problems, with a focus on the p?centre problem. Chapter 1 begins with a brief history of location problems, followed by the various classifications and methodologies used to solve them. Chapter 2 provides a review of the methods that have been used to solve the p?centre problem, with a focus on the continuous p?centre problem. An overview of the location models used in this research is given in Chapter 3, alongside an initial investigative work.
The next two chapters enhance two well-known optimal algorithms for the continuous p?centre problem. Chapter 4 develops an interesting exact algorithm that was first proposed over 30 years ago. The original algorithm is reexamined and efficient neighbourhood reductions which are mathematically supported are proposed to improve its overall computational performance. The enhanced algorithm shows a substantial reduction of up to 96% of required computational time compared to the original algorithm, and optimal solutions are found for large data sets that were previously unsolved. Chapter 5 develops a relatively new relaxation-based optimal method. Four mathematically supported enhancements are added to the algorithm to improve its efficiency and its overall computational time. The revised reverse relaxation algorithm yields a vast reduction of up to 87% of computational time required, which is then used to solve larger data sets where n ? 1323 optimally.
Chapter 6 creates a new relaxation-based matheuristic, called the relaxed p' matheuristic, by combining a well-known heuristic and the optimal method developed in Chapter 5. The unique property of the matheuristic is that it deals with the relaxation of facilities rather than demand points to establish a sub-problem. The matheuristic yields a good, but not necessarily optimal, solution in a reasonable time. To guarantee optimality, the results found from the matheuristic are embedded into the optimal algorithms developed in Chapters 4 and 5.
Chapter 7 adapts the optimal algorithm developed in Chapter 5 to solve two related location problems, namely the ??neighbour p?centre problem and the conditional p?centre problem. The ??neighbour p?centre problem is investigated and solved where ? = 2 & 3. A scenario analysis is also conducted for managerial insights by exploring changes in the number of facilities required to cover each demand point. Furthermore, an existing algorithm for the conditional p?centre problem is enhanced by incorporating the optimal algorithm proposed in Chapter 5, and it is used to solve large data sets where the number of preexisting facilities is 20. This chapter therefore demonstrates that an algorithm developed in this research can be adapted or used to enhance existing algorithms to optimally solve more practical and challenging related location problems.
Finally, Chapter 8 summarises the findings and main achievements of this research, and outlines any further work that could be worthwhile exploring in the future.
Wassan, N. (2016). Meta-Heuristics for the Multiple Trip Vehicle Routing Problem With Backhauls.
With the growing and more accessible computational power, the demand for robust and sophisticated computerised optimisation is increasing for logistical problems. By making good use of computational technologies, the research in this thesis concentrates on efficient fleet management by studying a class of vehicle routing problems and developing efficient solution algorithms.
The literature review in this thesis looks at VRPs from various development angles. The search reveals that from the problem modelling side clear efforts are made to bring the classical VRP models closer to reality by developing various variants. However, apart from the real VRP applications (termed as 'rich' VRPs), it is also noticeable that these classical VRP based variants address merely one or two additional characteristics from the real routing problem issues, concentrating on either operational (fleet management) or tactical (fleet acquisition) aspects. This thesis certainly hopes to add to one of those good efforts which have helped in bringing the VRPs closer to reality through addressing both the operational as well as the tactical aspects.
On the solution methodologies development side, the proposed research noted some considerable and impressive developments. Although, it is well established that the VRPs belong to the NP-hard combinatorial class of problems, there are considerable efforts on the development of exact methods. However the literature is full of a variety of heuristic methodologies including the classical and the most modern hybrid approaches. Among the hybrid approaches, the most recent one noted is mat-heuristics that combine heuristics and mathematical programming techniques to solve combinatorial optimisation problems. The mat-heuristics approaches appear to be comparatively in its infant age at this point in time. However this is an exciting area of research which seeks more attention in the literature. Hence, a good part of this research is devoted to the development of a hybrid approach that combines heuristics and mathematical programming techniques.
When reviewing the specific literature on the VRP problems focused in this thesis, the vehicle routing problem with backhauls (VRPB) and the multiple trip vehicle routing problem (MT-VRP), there is not sufficient development on the problem modelling side in terms of bringing these two problems closer to the reality. Hence, to fill the gap this thesis introduces and investigates a new variant, the multiple trip vehicle routing problem with backhauls (MT-VRPB) that combines the above two variants of the VRP. The problem is first described thoroughly and a new ILP (Integer Linear Programming) mathematical formulation of the MT-VRPB along with its possible variations is presented. The MT-VRPB is then solved optimally by using CPLEX along with providing an illustrative example showing the validation of the mathematical formulation. As part of the contribution, a large set of MT-VRPB data instances is created which is made available for future benchmarking.
The CPLEX implementation produced optimal solutions for a good number of small and medium size data instances of the MT-VRPB and generated lower bounds for all instances. The CPLEX success may be considered as modest, but the produced results proved very important for the validation of the heuristic results produced in the thesis.
To solve the larger instances of the MT-VRPB, a two level VNS algorithm called 'Two-Level VNS' is developed. It was noticed from the literature that the choice of using VNS for the VRPs has increased in recent literature due to its simplicity and speed. However our initial experiments with the classical VNS indicated that the algorithm is more inclined towards the intensification side. Hence, the Two-Level VNS is designed to obtain a maximum balance of the diversification and the intensification during the search process. It is achieved by incorporating a sub-set of neighbourhood structures and a sus-set of local search refinement routines and hence, a full set of neighbourhood structures and a full set of local search refinement routines at two levels of the algorithm respectively. The algorithm found very encouraging results when compared with the solutions found by CPLEX. These findings in this thesis demonstrate the power of VNS yet again in terms of its speed, simplicity and efficiency.
To investigate this new variant further, we developed an algorithm belonging to the new class of the hybrid methodologies, i.e., mat-heuristics. A hybrid collaborative sequential mat-heuristic approach called the CSMH to solve the MT-VRPB is developed. The exact method approach produced in Chapter 4 is then hybridised with the Two-Level VNS algorithm developed in Chapter 5. The overall performance of the CSMH remained very encouraging in terms of the solution quality and the time taken on average compared with the CPLEX and the Two-Level VNS meta-heuristic.
To demonstrate the power and effectiveness of our methodologies, we tested the designed algorithms on the two special versions of the VRP (i.e., VRPB and MT-VRP) to assess whether they are efficient and dynamic enough to solve a range of VRP variants. Hence the Two-Level VNS and the CSMH algorithms developed to solve the MT-VRPB are adapted accordingly and implemented to solve the two above variants separately. The algorithms produced very competitive results for the benchmark data sets when compared to the best known solutions from the literature. The successful implementations of these algorithms on the three VRP models with only minor amendments prove their generalizability and their robustness.
The results in this research show that significant cost savings could be obtained by choosing the right fleet size and better vehicle utilisations with multiple trips and backhauling. Hence, the research proved the justification of studying this interesting combination. Moreover, the problem modelling, efficient algorithm design and implementation, and the research results reveal some vital information and implications from the managerial point of view in terms of making the tactical (fleet acquisition) and the operational (fleet management) decisions in a more informative manner.