Search

This paper presents a new variant of the vehicle routing problem (VRP), the prize-collecting vehicle routing problem (PCVRP), which is derived from the hot rolling production of the iron and steel industry. One major characteristic of the PCVRP is that the customers need not be visited compulsorily but a prize can be collected from each customer when visited. Besides the capacity constraint, a task completion constraint is introduced and requires that the total demand of the visited customers should be no less than a predetermined amount. The main objective is a linear combination of three objectives: minimization of total distance traveled, minimization of vehicles used, and maximization of prizes collected. An iterated local search algorithm (ILS) based on very large-scale neighborhood (VLSN) using cyclic transfer is proposed for the PCVRP. Computational results of problem instances with up to 100 customers show the algorithm is efficient and effective. [ABSTRACT FROM AUTHOR]

In this paper, we present solution algorithms for the cycle hub location problem (CHLP), which seeks to locate p hub facilities that are connected by means of a cycle, and to assign non-hub nodes to hubs so as to minimize the total cost of routing flows through the network. This problem is useful in modeling applications in transportation and telecommunications systems, where large setup costs on the links and reliability requirements make cycle topologies a prominent network architecture. We present a branch-and-cut algorithm that uses a flow-based formulation and two families of mixed-dicut inequalities as a lower bounding procedure at nodes of the enumeration tree. We also introduce a metaheuristic based on greedy randomized adaptive search procedure to obtain initial upper bounds for the exact algorithm and to obtain feasible solutions for large-scale instances of the CHLP. Numerical results on a set of benchmark instances with up to 100 nodes and 8 hubs confirm the efficiency of the proposed solution algorithms. [ABSTRACT FROM AUTHOR]