A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization

Customer clustering is an essential step to reduce the complexity of large-scale logistics network optimization. By properly grouping those customers with similar characteristics, logistics operators are able to reduce operational costs and improve customer satisfaction levels. However, due to the heterogeneity and high-dimension of customers’ characteristics, the customer clustering problem has not been widely studied. This paper presents a fuzzy-based customer clustering algorithm with a hierarchical analysis structure to address this issue. Customers’ characteristics are represented using linguistic variables under major and minor criteria, and then, fuzzy integration method is used to map the sub-criteria into the higher hierarchical criteria based on the trapezoidal fuzzy numbers. A fuzzy clustering algorithm based on Axiomatic Fuzzy Set is developed to group the customers into multiple clusters. The clustering validity index is designed to evaluate the effectiveness of the proposed algorithm and find the optimal clustering solution. Results from a case study in Anshun, China reveal that the proposed approach outperforms the other three prevailing algorithms to resolve the customer clustering problem. The proposed approach also demonstrates its capability of capturing the similarity and distinguishing the difference among customers. The tentative clustered regions, determined by five decision makers in Anshun City, are used to evaluate the effectiveness of the proposed approach. The validation results indicate that the clustered results from the proposed method match the actual clustered regions from the real world well. The proposed algorithm can be readily implemented in practice to help the logistics operators reduce operational costs and improve customer satisfaction levels. In addition, the proposed algorithm is potential to apply in other research domains.     

The vehicle routing problem with multiple prioritized time windows: A case study

This paper addresses Multi-objective Vehicle Routing Problem with Multiple Prioritized Time Windows (VRPMPTW) in which the distributer proposes a set of all non-overlapping time windows with equal or different lengths and the customers prioritize these delivery time windows. VRPMPTW aims to find a set of routes of minimal total traveling cost and maximal customer satisfaction (with regard to the prioritized time windows), starting and ending at the depot, in such a way that each customer is visited by one vehicle given the capacity of the vehicle to satisfy a specific demand. This problem is inspired from a real life application. The contribution of this paper lies in its addressing the VRPMPTW from a problem definition, modeling and methodological point of view. We developed a mathematical model for this problem. This model can simply be used for a wide range of applications where the customers have multiple flexible time windows and violation of time windows may drop the satisfaction levels of customers and lead to profit loss in the long term. A Cooperative Coevolutionary Multi-objective Quantum-Genetic Algorithm (CCMQGA) is also proposed to solve this problem. A new local search is designed and used in CCMQGA to reach an appropriate pareto front. Finally, the proposed approach is employed in a real case study and the results of the proposed CCMQGA are compared with the current solution obtained from managerial experience, the results of NSGA-II and the multi-objective quantum-inspired evolutionary algorithm.     

A GRASP×ELS approach for the capacitated location-routing problem

This paper addresses the capacitated location-routing problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The CLRP is defined by a set of potential depot locations, with opening costs and limited capacities, a homogeneous fleet of vehicles, and a set of customers with known demands. The objective is to open a subset of depots, to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed solution method is a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS) and searching within two solution spaces: giant tours without trip delimiters and true CLRP solutions. Giant tours are evaluated via a splitting procedure that minimizes the total cost subject to vehicle capacity, fleet size and depot capacities. This framework is benchmarked on classical instances. Numerical experiments show that the approach outperforms all previously published methods and provides numerous new best solutions.     

Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services

In the field of high-value shipment transportation, companies are faced to the malevolence problem. The risk of ambush increases with the predictability of vehicle routes. This paper addresses a very hard periodic vehicle routing problem with time windows, submitted by a software company specialized in transportation problems with security constraints. The hours of visits to each customer over the planning horizon must be spread in the customer's time window. As the aim is to solve real instances, the running time must be reasonable. A mixed integer linear model and a multi-start iterated local search are proposed. Results are reported on instances derived from classical benchmarks for the vehicle routing problem with time windows, and on two practical instances. Experiments are also conducted on a particular case with a single period, the vehicle routing problem with soft time windows: the new metaheuristic competes with two published algorithms and improves six best known solutions.     

A decomposition-based heuristic for the multiple-product inventory-routing problem

The inventory-routing problem is an integrated logistics planning problem arising in situations where customers transfer the responsibility for inventory replenishment to the vendor. The vendor must then decide when to visit each customer, how much to deliver and how to sequence customers in vehicle routes. In this paper, we focus on the case where several different products have to be delivered by a fleet of vehicles over a finite and discrete planning horizon. We present a three-phase heuristic based on a decomposition of the decision process of the vendor. In the first phase, replenishment plans are determined by using a Lagrangian-based method. These plans do not specify delivery sequences for the vehicles. The sequencing of the planned deliveries is performed in the second phase in which a simple procedure is employed to construct vehicle routes. The third phase incorporates planning and routing decisions into a mixed-integer linear programming model aimed at finding a good solution to the integrated problem. Computational experiments show that our heuristic is effective on instances with up to 50 customers and 5 products.     

An improved formulation for the maximum coverage patrol routing problem

We present an improved formulation for the maximum coverage patrol routing problem (MCPRP). The main goal of the patrol routing problem is to maximize the coverage of critical highway stretches while ensuring the feasibility of routes and considering the availability of resources. By investigating the structural properties of the optimal solution, we formulate a new, improved mixed integer program that can solve real life instances to optimality within seconds, where methods proposed in prior literature fail to find a provably optimal solution within an hour. The improved formulation provides enhanced highway coverage for both randomly generated and real life instances. We show an average increase in coverage of nearly 20% for the randomly generated instances provided in the literature, with a best case increase over 46%. Similarly, for the real life instances, we close the optimality gap within seconds and demonstrate an additional coverage of over 13% in the best case. The improved formulation also allows for testing a number of real life scenarios related to multi-start routes, delayed starts at the beginning of the shifts, and taking a planned break during the shift. Being able to solve these scenarios in short durations help decision and policy makers to better evaluate resource allocation options while serving public.     

Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with time windows

A Dynamic Rich Vehicle Routing Problem with Time Windows has been tackled as a real-world application, in which customers requests can be either known at the beginning of the planning horizon or dynamically revealed over the day. Several real constraints, such as heterogeneous fleet of vehicles, multiple and soft time windows and customers priorities, are taken into consideration. Using exact methods is not a suitable solution for this kind of problems, given the fact that the arrival of a new request has to be followed by a quick re-optimization phase to include it into the solution at hand. Therefore, we have proposed a metaheuristic procedure based on Variable Neighborhood Search to solve this particular problem. The computational experiments reported in this work indicate that the proposed method is feasible to solve this real-world problem and competitive with the best results from the literature. Finally, it is worth mentioning that the software developed in this work has been inserted into the fleet management system of a company in Spain.     

Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading constraints are also considered. These constraints arise in many real‐world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.     

Solving the vehicle routing problem with adaptive memory programming methodology

In this paper we develop an adaptive memory programming method for solving the capacitated vehicle routing problem called Solutions’ Elite PArts Search (SEPAS). This iterative method, first generates initial solutions via a systematic diversification technique and stores their routes in an adaptive memory. Subsequently, a constructive heuristic merges route components (called elite parts) from those in the adaptive memory. Finally, a tabu search approach improves the heuristically constructed solution and the adaptive memory is appropriately updated. SEPAS has been tested on two benchmark data sets and provides high quality solutions in short computational times for all problem instances. The method reaches several new best solutions for benchmark instances with a large number of customers.     

Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies

This paper deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem (2E-HVRP) faced by Brazilian wholesale companies. Vehicle routing problems with more than one phase are known as Multi-Echelon VRP and consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin–Kernighan heuristic (IBMA-LK). In order to attest the algorithm’s efficiency, first it was tested in single echelon HVRP benchmark instances. After that the instances were adapted for two-echelon context and used for 2E-HVRP validation and, finally, it was tested on 2E-HVRP instances created using real world normalized data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.     

A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows

The time‐window‐constrained vehicle routing problem (VRPTW) is a well‐known combinatorial problem. Its goal is to discover the best set of routes for a vehicle fleet in order to service a given number of customers at minimum cost. Vehicle capacity, maximum service time and time‐window constraints must be satisfied. Most proposed VRPTW optimizing approaches intend to discover the best or a near‐optimal solution at once. Improvement methods are old strategies that apply heuristics to insert customers into tours and/or rearrange nodes to obtain better routes. They are performed until no further improvement is achieved. Little research has been focused on model‐based reactive approaches seeking a better solution by exploring a small solution space around the current solution. This work presents a new model‐based improvement methodology for the multi‐depot heterogeneous‐fleet VRPTW problem to enhance an initial solution through solving a series of MILP mathematical problems that allow exchanges of nodes among tours and node reordering on every route. By restricting the range of improvement options, the problem size can be bounded and a limited number of binary variables is required for real‐world problems. The improvement formulation is based on a continuous time‐domain representation that handles assignment and sequencing decisions through different sets of binary variables and uses the notion of a generalized predecessor instead of a direct predecessor. Several types of VRPTW problems have been efficiently solved.     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

New Models for Commercial Territory Design

In this work, a series of novel formulations for a commercial territory design problem motivated by a real-world case are proposed. The problem consists on determining a partition of a set of units located in a territory that meets multiple criteria such as compactness, connectivity, and balance in terms of customers and product demand. Thus far, different versions of this problem have been approached with heuristics due to its NP-completeness. The proposed formulations are integer quadratic programming models that involve a smaller number of variables than heretofore required. These models have also enabled the development of an exact solution framework, the first ever derived for this problem, that is based on branch and bound and a cut generation strategy. The proposed method is empirically evaluated using several instances of the new quadratic models as well as of the existing linear models. The results show that the quadratic models allow solving larger instances than the linear counterparts. The former were also observed to require fewer iterations of the exact method to converge. Based on these results the combination of the quadratic formulation and the exact method are recommended to approach problem instances associated with medium-sized cities.     

A solution method for a two-layer sustainable supply chain distribution model

This article presents an effective solution method for a two-layer, NP-hard sustainable supply chain distribution model. A DoE-guided MOGA-II optimiser based solution method is proposed for locating a set of non-dominated solutions distributed along the Pareto frontier. The solution method allows decision-makers to prioritise the realistic solutions, while focusing on alternate transportation scenarios. The solution method has been implemented for the case of an Irish dairy processing industry׳s two-layer supply chain network. The DoE generates 6100 real feasible solutions after 100 generations of the MOGA-II optimiser which are then refined using statistical experimentation. As the decision-maker is presented with a choice of several distribution routes on the demand side of the two-layer network, TOPSIS is applied to rank the set of non-dominated solutions thus facilitating the selection of the best sustainable distribution route. The solution method characterises the Pareto solutions from disparate scenarios through numerical and statistical experimentations. A set of realistic routes from plants to consumers is derived and mapped which minimises total CO₂ emissions and costs where it can be seen that the solution method outperforms existing solution methods.     

Modelization of Time-Dependent Urban Freight Problems by Using a Multiple Number of Distribution Centers

The aim of the paper is to model urban distribution vehicle routing problems by means of hubs in large cities. The idea behind the urban distribution center (DC) is to provide buffer points where cargo and packages which are to be delivered to shops and businesses can be stored beforehand. At these centers, there will be other kinds of routing problems corresponding to other fairly similar distribution problems. In this paper, a new vehicle routing model (based on the known Time-Dependent Vehicle Routing Problem with Time Windows, TDVRPTW) has been carried out and a change in the traditional approach is proposed, by adopting a system in which some customers are served by urban DCs while remaining customers are served by traditional routes. This study is also motivated by recent developments in real time traffic data acquisition systems, as well as national and international policies aimed at reducing concentrations of greenhouse gases emitted by traditional vans. By using k DCs, the whole problem is now composed of k+1 problems: one special VRPTW for each DC in addition to the main problem, in which some customers and k DC are serviced. The model has been tested by simulating one real case of pharmaceutical distribution within the city of Zaragoza.     

Application of a 3NN+1 based CBR system to segmentation of the notebook computers market

Case-based reasoning system (CBR) has been widely applied to the issue of market segmentation. Most of previous studies focused on dividing customers into two groups. Consequently, traditional voting method used for two groups in CBR would become inappropriate when one would like to divide customers into three groups through some segmentation variable. In this paper, a new voting method called 3NN+1 is proposed to bridge the gap. To make the inference of the 3NN+1 based CBR system more efficient, the features and instances (or cases) for reasoning is selected simultaneously by means of genetic algorithms. This new system is applied to a real case of notebook market to demonstrate its usefulness for market segmentation. From the results of the real case, it shows that the system would be valuable to enterprises, when dividing customers into three groups in compliance with their purchasing behaviors for developing marketing strategies.     

An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping

In this paper a vendor managed inventory (VMI) service in tramp shipping is considered. VMI takes advantage of introducing flexibility in delivery time and cargo quantities by transferring inventory management and ordering responsibilities to the vendor which in this case is a shipping company. A two-phase heuristic is proposed to determine routes and schedules for the shipping company. The heuristic first converts inventories into cargoes, thus turning the problem into a classic ship routing and scheduling problem. It then uses adaptive large neighborhood search to solve the resulting cargo routing and scheduling problem. The heuristic iteratively changes the cargoes generated to handle the customer’s inventories, based on the information obtained from an initial solution. Computational results are presented, discussed and compared with exact solutions on large realistic instances. The results reveal the potential savings from converting traditional contracts of affreightment to an integrated VMI service. The factors that influence the benefits obtainable through VMI are also analyzed.     

A decomposition approach for the p-median problem on disconnected graphs

The p-median problem seeks for the location of p facilities on the vertices (customers) of a graph to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities. In many real applications of the p-median problem the underlying graph is disconnected. That is the case of p-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem. In such cases the problem can be decomposed into smaller p-median problems which are solved in each component k for different feasible values of p_k, and the global solution is obtained by finding the best combination of p_k medians. This approach has the advantage that it permits to solve larger instances since only the sizes of the connected components are important and not the size of the whole graph. However, since the optimal number of facilities to select from each component is not known, it is necessary to solve p-median problems for every feasible number of facilities on each component. In this paper we give a decomposition algorithm that uses a procedure to reduce the number of subproblems to solve. Computational tests on real instances of the optimal diversity management problem and on simulated instances are reported showing that the reduction of subproblems is significant, and that optimal solutions were found within reasonable time.     

A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing

This paper presents an extension of a competitive vehicle routing problem with time windows (VRPTW) to find short routes with the minimum travel cost and maximum sale by providing good services to customers before delivering the products by other rival distributors. In distribution of the products with short life time that customers need special device for keeping them, reaching time to customers influences on the sales amount which the classical VRPs are unable to handle these kinds of assumptions. Hence, a new mathematical model is developed for the proposed problem and for solving the problem, a simulated annealing (SA) approach is used. Then some small test problems are solved by the SA and the results are compared with obtained results from Lingo 8.0. For large-scale problems, the, Solomon's benchmark instances with additional assumption are used. The results show that the proposed SA algorithm can find good solutions in reasonable time.     

A template-based Tabu Search algorithm for the Consistent Vehicle Routing Problem

This paper presents a generic template-based solution framework and its application to the so-called Consistent Vehicle Routing Problem (ConVRP). The ConVRP is an NP-hard combinatorial optimization problem and involves the design of a set of minimum cost vehicle routes to service a set of customers with known demands over multiple days. Customers may receive service either once or with a predefined frequency; however frequent customers must receive consistent service, i.e., must be visited by the same driver over approximately the same time throughout the planning period. The proposed solution framework adopts a two-level master-slave decomposition scheme. Initially, a master template route schedule is constructed in an effort to determine the service sequence and assignment of frequent customers to vehicles. On return, the master template is used as the basis to design the actual vehicle routes and service schedules for both frequent and non-frequent customers over multiple days. To this end, a Tabu Search improvement method is employed that operates on a dual mode basis and modifies both the template routes and the actual daily schedules in a sequential fashion. Computational experiments on benchmark data sets illustrate the competitiveness of the proposed approach compared to existing results.