An effective VNS for the capacitated p-median problem

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.     

The Clustered Orienteering Problem

In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch-and-cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem

In the capacitated team orienteering problem (CTOP), we are given a set of homogeneous vehicles and a set of customers each with a service demand value and a profit value. A vehicle can get the profit of a customer by satisfying its demand, but the total demand of all customers in its route cannot exceed the vehicle capacity and the length of the route must be within a specified maximum. The problem is to design a set of routes that maximizes the total profit collected by the vehicles. In this article, we propose a new heuristic algorithm for the CTOP using the ejection pool framework with an adaptive strategy and a diversification mechanism based on toggling between two priority rules. Experimental results show that our algorithm can match or improve all the best known results on the standard CTOP benchmark instances proposed by Archetti et al. (2008).     

A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints

Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

A greedy look-ahead heuristic for the vehicle routing problem with time windows

In this paper we consider the problem of physically distributing finished goods from a central facility to geographically dispersed customers, which pose daily demands for items produced in the facility and act as sales points for consumers. The management of the facility is responsible for satisfying all demand, and promises deliveries to the customers within fixed time intervals that represent the earliest and latest times during the day that a delivery can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns such as vehicle capacity, delivery time intervals and all relevant costs. The model, which is a case of the vehicle routing problem with time windows, is solved using a new heuristic technique. Our solution method, which is based upon Atkinson's greedy look-ahead heuristic, enhances traditional vehicle routing approaches, and provides surprisingly good performance results with respect to a set of standard test problems from the literature. The approach is used to determine the vehicle fleet size and the daily route of each vehicle in an industrial example from the food industry. This actual problem, with approximately two thousand customers, is presented and solved by our heuristic, using an interface to a Geographical Information System to determine inter-customer and depot–customer distances. The results indicate that the method is well suited for determining the required number of vehicles and the delivery schedules on a daily basis, in real life applications.     

A mixed-integer programming approach to the clustering problem with an application in customer segmentation

This paper presents a mathematical programming based clustering approach that is applied to a digital platform company’s customer segmentation problem involving demographic and transactional attributes related to the customers. The clustering problem is formulated as a mixed-integer programming problem with the objective of minimizing the maximum cluster diameter among all clusters. In order to overcome issues related to computational complexity of the problem, we developed a heuristic approach that improves computational times dramatically without compromising from optimality in most of the cases that we tested. The performance of this approach is tested on a real problem. The analysis of our results indicates that our approach is computationally efficient and creates meaningful segmentation of data.     

The open vehicle routing problem with time windows

In this paper, we consider the open vehicle routing problem with time windows (OVRPTW). The OVRPTW seeks to find a set of non-depot returning vehicle routes, for a fleet of capacitated vehicles, to satisfy customers’ requirements, within fixed time intervals that represent the earliest and latest times during the day that customers’ service can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns. The model is solved using a greedy look-ahead route construction heuristic algorithm, which utilizes time windows related information via composite customer selection and route-insertion criteria. These criteria exploit the interrelationships between customers, introduced by time windows, that dictate the sequence in which vehicles must visit customers. Computational results on a set of benchmark problems from the literature provide very good results and indicate the applicability of the methodology in real-life routing applications.     

Lasso solution strategies for the vehicle routing problem with pickups and deliveries

This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort.     

Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery

We consider the problem of finding the optimal routing of a single vehicle that starts its route from a depot and picks up from and delivers K different products to N customers that are served according to a predefined customer sequence. The vehicle is allowed during its route to return to the depot to unload returned products and restock with new products. The items of all products are of the same size. For each customer the demands for the products that are delivered by the vehicle and the quantity of the products that is returned to the vehicle are discrete random variables with known joint distribution. Under a suitable cost structure, it is shown that the optimal policy that serves all customers has a specific threshold-type structure. We also study a corresponding infinite-time horizon problem in which the service of the customers is not completed when the last customer has been serviced but it continues indefinitely with the same customer order. For each customer, the joint distribution of the quantities that are delivered and the quantity that is picked up is the same at each cycle. The discounted-cost optimal policy and the average-cost optimal policy have the same structure as the optimal policy in the finite-horizon problem. Numerical results are given that illustrate the structural results.     

Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network

This paper addresses a generalization of the capacitated location-routing problem (CLRP) arising in the design of a collection network for a company engaged in collecting used products from customer zones. The company offers customers a financial incentive per unit of used products. This incentive determines the quantity of used products which are returned by customers. Moreover, it is not necessary for the company to visit all customer zones or to collect all returns in each visited customer zone. The objective is to simultaneously find the location of collection centers, the routes of vehicles, the value of incentive offered and the amount of used products collected from customer zones, so as to maximize the company's overall profit. We develop two mixed integer linear programming formulations of the problem and a heuristic algorithm based on iterated local search. Extensive computational experiments on this problem demonstrate the effectiveness of the proposed algorithm.     

Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

A column generation heuristic for districting the price of a financial product

This paper studies a districting problem that arises in the context of financial product pricing. The challenge lies in partitioning a set of small geographical regions into a set of larger territories. In each territory, the customers will share a common price. These territories need to be contiguous, contain enough customers and be as homogeneous as possible in terms of customer value. To address this problem, we present a column generation-based heuristic where the subproblem generates contiguous territories taken into account a nonlinear objective function. Computational results indicate that the territories produced by this heuristic are about 35% more homogeneous than those previously used in practice. The developed algorithm has been transferred to a financial firm and is now used to help craft more competitive financial products.     

Vehicle routing with a sparse feasibility graph

In this paper we introduce the concept of a feasibility graph for vehicle routing problems, a graph where two customers are linked if and only if it is possible for them to be successive (adjacent) customers on some feasible vehicle route. We consider the problem of designing vehicle routes when the underlying feasibility graph is sparse, i.e. when any customer has only a few other customers to which they can be adjacent on a vehicle route. This problem arose during a consultancy study that involved the design of fixed vehicle routes delivering to contiguous (adjacent) postal districts. A heuristic algorithm for the problem is presented and computational results given for a number of test problems involving up to 856 customers.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

线型/圈型网络上单台车辆分群调度问题

本文研究线型/圈型网络上单台车辆分群调度问题。给定一个线型/圈型网络,若干客户分布其中。所有客户被划分成若干个子集,每个子集称为一个群。每个客户有一个释放时间和一个服务时间。给定一台车辆,其需要服务所有客户,且每个群内的客户连续服务。问题的要求是计算一个时间表,使得车辆能够按要求服务完所有客户并返回初始出发位置所花费的时间最少。针对该问题,就线型网络和圈型网络,分别给出一个7/4和一个13/7近似算法。     

Kernel search for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is among the most studied problems in the OR literature. Each customer demand has to be supplied by one or more facilities. Each facility cannot supply more than a given amount of product. The goal is to minimize the total cost to open the facilities and to serve all the customers. The problem is $\mathcal{NP}$ -hard. The Kernel Search is a heuristic framework based on the idea of identifying subsets of variables and in solving a sequence of MILP problems, each problem restricted to one of the identified subsets of variables. In this paper we enhance the Kernel Search and apply it to the solution of the CFLP. The heuristic is tested on a very large set of benchmark instances and the computational results confirm the effectiveness of the Kernel Search framework. The optimal solution has been found for all the instances whose optimal solution is known. Most of the best known solutions have been improved for those instances whose optimal solution is still unknown.