A Heavy‐Duty Vehicle Routing Problem With Temperature Constraints

ABSTRACT This article studies a vehicle routing problem involving a fleet of heavy‐duty vehicles and pickup‐and‐delivery requests for crude items that are both heavy and high‐temperature. The objective is to route the fleet in such a way that maximizes resource efficiency and operational efficiency while simultaneously avoiding thermal overload of any vehicle in the fleet. This is achieved by considering the curb weight of the vehicles and the weight of the items being transported when optimizing vehicle routing. Additionally, transshipments of items en route are considered. To maintain the fleet's mechanical preservation, thermal overload of the vehicles must be avoided. Therefore, temperatures of items and vehicles, as well as their interdependence, are considered. We introduce the vehicle temperature predictor, which is based on Newton's law of cooling and allows us to estimate the vehicle temperature en route. However, considering the vehicle temperature presents two challenges. First, solution feasibility is often jeopardized by vehicle temperature constraints. Second, solutions are produced that are heat‐efficient but not resource‐efficient. Our metaheuristic solution framework addresses both challenges by means of a large neighborhood search using adapted, novel, and feature‐based heuristics. We provide valuable insights into resource‐efficient and heat‐efficient routing policies by experimenting with test instances that mimic real‐world data from a partnered steel plant. Additionally, we present a mixed integer nonlinear programming formulation and demonstrate the effectiveness of our proposed metaheuristic solution approach by obtaining optimal solutions for small test instances.