Plug-in hybrid electric refuse vehicle routing problem for waste collection

• Waste Collection Vehicle Routing Problem with Time Windows is studied. • Compressed natural gas plug-in hybrid electric vehicles are investigated. • A new Hybrid Threshold Acceptance algorithm is presented. • Extensive computational experiments are carried out. Commercial waste collection is an essential service requiring efficient and reliable provision for customers. At the operational level, one of the most challenging problems is to design a set of refuse vehicle routes to collect waste from a set of bins. To be used multiple times, these vehicles must be emptied regularly throughout the day. This paper investigates a waste collection problem with a homogeneous fleet of plug-in hybrid electric refuse vehicles powered by two different power sources, i.e., electricity and compressed natural gas (CNG). In addition, realistic fuel consumption functions are used to estimate total energy requirements for each type of fuel, including refueling and recharging, and the detailed energy consumption along the path between two nodes of interest. We propose a Hybrid Threshold Acceptance (HTA) algorithm for this problem and denote it as the Hybrid Waste Collection Problem (HWCP). Extensive computational experiments confirm that the proposed HTA algorithm provides good results against current state-of-the-art algorithms designed for the electric vehicle routing problem. Out detailed computational results demonstrate the performance of our method considering either full or partial recharging, as well as the effect of different battery/tank capacities. Compared to the standard CNG or electric vehicles, we also show the benefits of using a fleet of hybrid electric refuse vehicles in terms of operational costs and total distance traveled.