Today’s Patent – Quantum-Classical Solution Stack for Vehicle Routing Problem

The said invention (US11816606B2) was invented by Vaibhaw Kumar, Dimitrios Alevras, Imed Othmani, patented by USPTO on 05-12-2021. Currently, it stands assigned to International Business Machines Corp.

The present disclosure generally relates to routing technology, and more particularly, to advanced computing architectures that are configured to process complex routing scenarios. A vehicle routing problem (VRP) relates to a combinatorial optimization and integer programming task that attempts to provide an optimal set of routes for a fleet of vehicles to travel to a predetermined set of destination points. A capacitated VRP with Time-Windows involves finding optimal set of routes that incurs least cost given the capacity of the vehicle, demands at each destination location, service times, and time-windows for the delivery. Obtaining effective solutions to such a problem is salient for various industries, such as, without limitation, transportation, manufacturing, telecommunications, utilities and energy, as well as the public sector. The problem is highly complex and is known to be NP-hard (non-deterministic polynomial time hard) and may not be solved efficiently, if at all, with conventional computing architectures.

A method and system of generating a route includes receiving information regarding a set of nodes to be serviced. One or more parameters of each node are determined. A capacity of each of the one or more vehicles is determined. A classical computer is used to generate a set of feasible routes based on the one or more parameters of each node and the capacity of each of the one or more vehicles. A number of bags N to divide the set of feasible routes is determined. The feasible routes are distributed into the N bags. The N bags are sent to a quantum computer to calculate a most efficient combination of feasible routes that cover all nodes to be serviced.