DESC:RESERVATION OF RIGHTS
[1] A portion of the disclosure of this patent document contains material, which is subject to intellectual property rights such as, but are not limited to, copyright, design, trademark, Integrated Circuit (IC) layout design, and/or trade dress protection, belonging to Jio Platforms Limited (JPL) or its affiliates (hereinafter referred as owner). The owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights whatsoever. All rights to such intellectual property are fully reserved by the owner.

FIELD OF DISCLOSURE
[2] The embodiments of the present disclosure generally relate to quantum computing applications for logistics optimization in supply chain. More particularly, the present disclosure relates to a hybrid classical-quantum optimization system and method for solving the capacitated vehicle routing problem applied to a retail supply chain.

BACKGROUND OF DISCLOSURE
[3] The following description of related art is intended to provide background information pertaining to the field of the disclosure. This section may include certain aspects of the art that may be related to various features of the present disclosure. However, it should be appreciated that this section be used only to enhance the understanding of the reader with respect to the present disclosure, and not as admissions of prior art.
[4] Capacitated vehicle routing problem (CVRP) is a vehicle routing problem associated with vehicles having limited carrying capacity. The vehicles need to pick up or deliver items at various locations, wherein the items have a quantity, such as weight or volume. The vehicles have a maximum capacity that they can carry. Hence, optimization in terms of the number of pickup points and the number of items that may be delivered by the vehicles is required making CVRP as a well-known non-deterministic polynomial (NP) hard logistics problem. Such NP hard problems do not have a proper solution on a classical computer.
[5] Over recent years, several solutions to the CVRP involving quantum computing, have been developed. However, the CVRP is a comparatively larger problem to solve on a quantum computer as compared to its simpler variant, the Travelling Salesman Problem (TSP). As a result, several heuristics have been developed to reduce the CVRP to a TSP form that is easily solvable on a quantum computer.
[6] The solutions, however, are only able to handle a fixed number of vehicles. There are no techniques for handling situations where the number of vehicles is also an optimization parameter or situations where no feasible solution is found with the given number of vehicles under the given capacity constraints.
[7] There is, therefore, a need in the art to provide a method and a system that can overcome the shortcomings of the existing prior arts.

SUMMARY
[8] This section is provided to introduce certain objects and aspects of the present disclosure in a simplified form that are further described below in the detailed description. This summary is not intended to identify the key features or the scope of the claimed subject matter.
[9] In one aspect, the present disclosure relates to a system for solving capacitated vehicle routing problem (CVRP) in a vehicular network. The system includes one or more processors and a memory operatively coupled to the one or more processors, wherein the memory includes processor-executable instructions, which on execution, cause the one or more processors to obtain one or more optimized routes, from a source node to one or more destination nodes, for at least one vehicle of a plurality of vehicles in the vehicular network, wherein the one or more destination nodes are traversed one time by the at least one vehicle, create a partition graph, including the source node, the one or more destination nodes, and one or more edges between the source node and the one or more destination nodes, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network, assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph, and determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle and the weight value assigned in the partition graph.
[10] In some embodiments, the one or more processors may be configured to assign the determined shortest route to the at least one vehicle of the plurality of vehicles in the vehicular network.
[11] In some embodiments, the source node includes a starting point for the at least one vehicle, the one or more destination nodes include one or more delivery stops for the at least one vehicle, and the one or more edges include a route traversed by the at least one vehicle from the source node to the one or more destination nodes.
[12] In some embodiments, the number of edges in the partition graph is equal to a number of the plurality of vehicles in the vehicular network.
[13] In some embodiments, the one or more processors may be configured to create a plurality of clusters based on at least one of the capacity of the vehicle and a time constraint associated with the vehicle, assign at least one cluster of the plurality of clusters to the at least one vehicle, and determine the one or more optimized routes for the at least one vehicle based on the assignment of the at least one cluster and quantum annealing techniques.
[14] In another aspect the present disclosure relates to a method for solving capacitated vehicle routing problem (CVRP) in a vehicular network. The method includes obtaining, by one or more processors associated with a system, one or more optimized routes, from a source node to one or more destination nodes, for at least one vehicle of a plurality of vehicles in the vehicular network, wherein the one or more destination nodes are traversed one time by the at least one vehicle, creating, by the one or more processors, a partition graph, including the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network, assigning, by the one or more processors, a demand value to the source node and the one or more destination nodes, and a weight value to the one or mode edges in the partition graph; and determining, by the one or more processors, a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle and the weight value assigned in the partition graph.
[15] In some embodiments, the method includes assigning, by the one or more processors, the determined shortest route to the at least one vehicle of the plurality of vehicles in the vehicular network.
[16] In some embodiments, the method may include creating, by the one or more processors, a plurality of clusters based on at least one of the capacity of the vehicle and a time constraint associated with the vehicle, assigning, by the one or more processors, at least one cluster of the plurality of clusters to the at least one vehicle, and determining, by the one or more processors, the one or more optimized routes for the at least one vehicle based on the assignment of the at least one cluster and quantum annealing techniques.
[17] In one another aspect, the present disclosure relates to a user equipment (UE). The UE includes a processor communicatively coupled to a system, wherein the system includes one or more processors operatively couple to a memory having processor-executable instructions, which on execution, cause the one or more processors to obtain one or more optimized routes, from a source node to one or more destination nodes, for at least one vehicle of a plurality of vehicles in a vehicular network, wherein the one or more destination nodes are traversed one time by the at least one vehicle, create a partition graph, including the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network, assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph, and determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle, the demand value, and the weight value assigned in the partition graph.
[18] In yet another aspect, the present disclosure relates to a non-transitory computer readable medium that includes one or more instructions stored thereupon that when executed by a processor causes the processor to obtain one or more optimized routes, from a source node to one or more destination nodes, for at least one vehicle of a plurality of vehicles in a vehicular network, wherein the one or more destination nodes are traversed one time by the at least one vehicle, create a partition graph, including the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network, assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph, and determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle, the demand value and the weight value assigned in the partition graph.

OBJECTS OF THE PRESENT DISCLOSURE
[19] Some of the objects of the present disclosure, which at least one embodiment herein satisfies are as listed herein below.
[20] It is an object of the present disclosure to solve the capacitated vehicle routing problem (CVRP) using a hybrid classical-quantum algorithm.
[21] It is an object of the present disclosure to handle a fixed number of vehicles as well as optimize over the number of vehicles.
[22] It is an object of the present disclosure to implement a shortest path finding algorithm to determine optimal partitioning of routes obtained based on quantum travelling salesman problem (TSP) solution for the CVRP.
[23] It is an object of the present disclosure to provide a customized shortest path finding algorithm for finding the shortest path involving at most k hops in a graph.
[24] It is an object of the present disclosure to find the optimal number of vehicles to complete a task, if partitioning is not possible with the given number of vehicles.

BRIEF DESCRIPTION OF DRAWINGS
[25] The accompanying drawings, which are incorporated herein, and constitute a part of this disclosure, illustrate exemplary embodiments of the disclosed methods and systems in which like reference numerals refer to the same parts throughout the different drawings. Components in the drawings are not necessarily to scale, emphasis instead being placed upon clearly illustrating the principles of the present disclosure. Some drawings may indicate the components using block diagrams and may not represent the internal circuitry of each component. It will be appreciated by those skilled in the art that disclosure of such drawings includes the disclosure of electrical components, electronic components or circuitry commonly used to implement such components.
[26] FIG. 1A illustrates an exemplary network architecture (100) in which or with which proposed system may be implemented for solving capacitated vehicle routing problem (CVRP), in accordance with an embodiment of the present disclosure.
[27] FIG. 1B illustrates an exemplary representation of a capacitated vehicle routing network (100-B), in accordance with an embodiment of the present disclosure.
[28] FIG. 2 illustrates an exemplary representation (200) of a quantum processing unit for solving CVRP, in accordance with an embodiment of the present disclosure.
[29] FIG. 3 illustrates an exemplary flow diagram (300) of a genetic algorithm (GA) for solving the CVRP.
[30] FIG. 4A illustrates an exemplary flow diagram (400-A) of a simulated annealing process for solving the CVRP.
[31] FIG. 4B illustrates a quantum tunnelling mechanism (400-B) associated with a quantum annealing process.
[32] FIG. 4C illustrates an energy diagram (400-C) associated with the quantum annealing process.
[33] FIG. 5 illustrates a flow diagram (500) associated with the quantum annealing process for solving CVRP.
[34] FIG. 6 illustrates a flow diagram (600) of a density-based clustering algorithm (DBSCAN) for obtaining vehicle routes.
[35] FIG. 7A illustrates a flow diagram (700-A) for determining vehicle route, in accordance with an embodiment of the present disclosure.
[36] FIG. 7B illustrates a flow diagram (700-B) for finding a shortest path in a partition graph, in accordance with an embodiment of the present disclosure.
[37] FIG. 8A illustrates a graph representation (800-A) of vehicle routes obtained by applying a travelling salesman problem (TSP) to the number of vehicles in the network (100), in accordance with an embodiment of the present disclosure.
[38] FIG. 8B illustrates a partitioning graph (800-B) formed based on the vehicle routes obtained using TSP, in accordance with an embodiment of the present disclosure.
[39] FIG. 8C illustrates a shortest path (800-C) obtained on the partitioning graph, in accordance with an embodiment of the present disclosure.
[40] FIG. 8D illustrates vehicle routes (800-D) determined based on the shortest path, in accordance with an embodiment of the present disclosure.
[41] FIG. 9 illustrates an exemplary computer system (900) in which or with which embodiments of the present disclosure may be implemented.
[42] The foregoing shall be more apparent from the following more detailed description of the disclosure.

DETAILED DESCRIPTION OF DISCLOSURE
[43] In the following description, for the purposes of explanation, various specific details are set forth in order to provide a thorough understanding of embodiments of the present disclosure. It will be apparent, however, that embodiments of the present disclosure may be practiced without these specific details. Several features described hereafter can each be used independently of one another or with any combination of other features. An individual feature may not address all of the problems discussed above or might address only some of the problems discussed above. Some of the problems discussed above might not be fully addressed by any of the features described herein.
[44] The ensuing description provides exemplary embodiments only, and is not intended to limit the scope, applicability, or configuration of the disclosure. Rather, the ensuing description of the exemplary embodiments will provide those skilled in the art with an enabling description for implementing an exemplary embodiment. It should be understood that various changes may be made in the function and arrangement of elements without departing from the spirit and scope of the disclosure as set forth.
[45] Specific details are given in the following description to provide a thorough understanding of the embodiments. However, it will be understood by one of ordinary skill in the art that the embodiments may be practiced without these specific details. For example, circuits, systems, networks, processes, and other components may be shown as components in block diagram form in order not to obscure the embodiments in unnecessary detail. In other instances, well-known circuits, processes, algorithms, structures, and techniques may be shown without unnecessary detail in order to avoid obscuring the embodiments.
[46] Also, it is noted that individual embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be re-arranged. A process is terminated when its operations are completed but could have additional steps not included in a figure. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, its termination can correspond to a return of the function to the calling function or the main function.
[47] The word “exemplary” and/or “demonstrative” is used herein to mean serving as an example, instance, or illustration. For the avoidance of doubt, the subject matter disclosed herein is not limited by such examples. In addition, any aspect or design described herein as “exemplary” and/or “demonstrative” is not necessarily to be construed as preferred or advantageous over other aspects or designs, nor is it meant to preclude equivalent exemplary structures and techniques known to those of ordinary skill in the art. Furthermore, to the extent that the terms “includes,” “has,” “contains,” and other similar words are used in either the detailed description or the claims, such terms are intended to be inclusive—in a manner similar to the term “comprising” as an open transition word—without precluding any additional or other elements.
[48] Reference throughout this specification to “one embodiment” or “an embodiment” or “an instance” or “one instance” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present disclosure. Thus, the appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.
[49] The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the disclosure. As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.
[50] In some aspect, the present disclosure provides a robust and effective solution for a capacitated vehicle routing problem (CVRP) for vehicles used in retail supply chain. In some embodiments, a hybrid classical quantum based approach is implemented for finding the shortest path that may be assigned to a delivery vehicle. In some embodiments, optimized routes associated with the delivery vehicle is determined based on solving a travelling salesman problem (TSP) using quantum algorithm, creating a partitioning graph on the obtained routes based on the number of vehicles and demand and weight parameters associated with the vehicles, and determining a shortest path on the portioning graph based on any of the classical shortest path algorithms. The determined shortest path may be assigned to the delivery vehicle for delivering the items or goods it is carrying to one more users or customer.
[51] The various embodiments throughout the disclosure will be explained in more detail with reference to FIGs. 1-9.
[52] FIG. 1A illustrates an exemplary network architecture (100) in which or with which proposed system may be implemented for solving capacitated vehicle routing problem (CVRP), in accordance with an embodiment of the present disclosure.
[53] Referring to FIG. 1A, the network (100) includes a quantum computing device (110) having a quantum solver module (108) for obtaining one or more optimized routes from a source to a destination based on a travelling salesman problem (TSP) using quantum annealing process and a shortest path solver module (112) for obtaining a shortest path based on a partitioning graph obtained based on the one or more optimized route. In some embodiments, the network (100) may include a vehicular network and the shortest path may be assigned to one or more vehicles (102-1, 102-2…102-N) in the vehicular network.
[54] Referring to FIG. 1A, the one or more vehicles (102-1, 102-2...102-N) (collectively referred to as vehicles (102) and individually referred to as vehicle (102)) are associated with one or more computing devices (104-1, 104-2…104-N) (collectively referred to as computing devices (104) and individually referred to as computing device (104)). In some embodiments, the computing device (104) may contain a set of vehicle information such as routing information, location of one more delivery points for the vehicle, capacity of the vehicles (102), etc.
[55] In an embodiment, each computing device (104) may interoperate with every other computing device (104) in the network architecture (100). In an embodiment, the computing devices (104) may be referred to as a user equipment (UE). A person of ordinary skill in the art will appreciate that the terms “computing device(s)” and “UE” may be used interchangeably throughout the disclosure.
[56] In an embodiment, the computing devices (104) may include, but are not limited to, a handheld wireless communication device (e.g., a mobile phone, a smart phone, a phablet device, and so on), a wearable computer device (e.g., a head-mounted display computer device, a head-mounted camera device, a wristwatch computer device, and so on), a Global Positioning System (GPS) device, a laptop computer, a tablet computer, or another type of portable computer, a media playing device, a portable gaming system, and/or any other type of computer device (104) with wireless communication capabilities, and the like. In an embodiment, the computing devices (104) may include, but are not limited to, any electrical, electronic, electro-mechanical, or an equipment, or a combination of one or more of the above devices such as virtual reality (VR) devices, augmented reality (AR) devices, laptop, a general-purpose computer, desktop, personal digital assistant, tablet computer, mainframe computer, or any other computing device, wherein the computing device (104) may include one or more in-built or externally coupled accessories including, but not limited to, a visual aid device such as camera, audio aid, a microphone, a keyboard, and input devices for receiving input from a user associated with the vehicle (102) such as touch pad, touch enabled screen, electronic pen, and the like.
[57] In an embodiment, the computing devices (104) may include, but are not limited to, smart phones, smart watches, smart sensors (e.g., mechanical, thermal, electrical, magnetic, etc.), networked appliances, networked peripheral devices, networked lighting system, communication devices, networked vehicle accessories, smart accessories, tablets, smart television (TV), computers, smart security system, smart home system, other devices for monitoring or interacting with or for users and/or places, or any combination thereof. In an embodiment, the computing devices (104) may include one or more of the following components: sensor, radio frequency identification (RFID) technology, GPS technology, mechanisms for real-time acquisition of data, passive or interactive interface, etc.
[58] A person of ordinary skill in the art will appreciate that the computing devices or UEs (104) may not be restricted to the mentioned devices and various other devices may be used.
[59] Referring to FIG. 1A, the computing devices (104) may communicate with the quantum computing device (110), for example, a shortest path finding system, through a network (106). In an embodiment, the network (106) may include at least one of a Fourth Generation (4G) network, a Fifth Generation (5G) network, or the like. The network (106) may enable the computing devices (104) to communicate between devices (104) and/or with the system (110). As such, the network (106) may enable the computing devices (104) to communicate with other computing devices (104) via a wired or wireless network. The network (106) may include a wireless card or some other transceiver connection to facilitate this communication. In an exemplary embodiment, the network (106) may incorporate one or more of a plurality of standard or proprietary protocols including, but not limited to, Wi-Fi, Zigbee, or the like. In another embodiment, the network (106) may be implemented as, or include any of a variety of different communication technologies such as a wide area network (WAN), a local area network (LAN), a wireless network, a mobile network, a Virtual Private Network (VPN), the Internet, the Public Switched Telephone Network (PSTN), or the like.
[60] Referring to FIG. 1A, the quantum computing device (110) may be configured to receive location of a plurality of nodes the one or more vehicles (102) are traversing through. In an example embodiment, the one or more vehicles (102) may include a delivery vehicle and the plurality of nodes may indicate cities, towns, villages, localities, individual houses/plots/apartments at which the delivery vehicle makes a stop during a trip. The trip may refer to travelling of the delivery vehicle (102) from a reference location or a source node to all the other nodes or target nodes or destination nodes and then come back to the source node after traversing through all the target nodes at least one time. In some embodiment, the quantum computing device (110) may receive a set of distances associated with the source node to the one or more target nodes and may apply one or more quantum processing algorithms, for example, a travelling salesman problem (TSP) using quantum annealing techniques to determine one or more optimized routes from the source node to the one or more target nodes, such that the target nodes are traversed one time by the delivery vehicle (102). In some embodiments, the quantum solver module (108) may apply at least one quantum annealing technique, for example, without limitations, a quadratic unconstrained binary optimization (QUBO) solver or a density-based spatial clustering of applications with noise (DBSCAN) Solver to obtain the optimized routes.
[61] Referring to FIG. 1A, the quantum computing device (110) further includes the shortest path solver module (112) to determine a shortest path based on optimized routes obtained by the quantum solver module (108). In some embodiments, the shortest path may be obtained by obtaining a partitioning graph based on the optimized routes determined by the quantum solver module (108) and applying at least one shortest path algorithm, for example, without limitations, Djikstra’s algorithm or Bellman-Ford algorithm. The shortest path obtained may be assigned to the one or more delivery vehicles (102).
[62] In some embodiments, the shortest path assigned may be communicated by the quantum computing device (110) to the computing device (104) via the network (106). Further, the computing device may instruct the vehicle (102) associated with the computing device (104) about the assigned shortest path route and the vehicle (102) may take the assigned shortest path as its route to complete the delivery task.
[63] Although FIG. 1 shows exemplary components of the network architecture (100), in other embodiments, the network architecture (100) may include fewer components, different components, differently arranged components, or additional functional components than depicted in FIG. 1. Additionally, or alternatively, one or more components of the network architecture (100) may perform functions described as being performed by one or more other components of the network architecture (100).
[64] FIG. 1B illustrates an exemplary representation of a capacitated vehicle routing network (100-B), in accordance with an embodiment of the present disclosure.
[65] Referring to FIG. 1B, the capacitated vehicle routing network or a vehicular network (100-B) includes a depot or source node (114), one or more destination or target nodes represented as nodes (1, 2, 3, 4,5, 6, 7, 8, 9), and one or more vehicles (102-1, 102-2, 102-3, 104-4). In some embodiments, the one or more vehicles (102-1, 102-2, 102-3, 104-4), may start from the depot or source node (114) and travel the one or more destination or target node (1-9) and return back to the source node (114). In an example embodiment, the vehicle (102-1) may travel from the source node (114) to the target node (1) and the return back to the source node. Similarly, the vehicle (102-2) may travel from the source node (114) to the destination nodes (3, 2) and the return to the source node, vehicle (102-3) may make a round trip from the source node (114) through destination nodes (4, 5, 9, and 8), and vehicle (102-4) may make a round trip from the source node (114) through destination nodes (6 and 7). In some embodiments, the quantum computing device (110) as shown in FIG. 1A may determine the shortest path that may be taken by the vehicle (102) from the source node (114) to the one or more destination nodes (1-9), and the determined shortest path may be assigned to the vehicle (102).
[66] FIG. 2 illustrates an exemplary representation (200) of a quantum computing device (110) for solving the CVRP, in accordance with an embodiment of the present disclosure.
[67] Referring to FIG. 2, the quantum computing device or a quantum computing system (110) (herein after referred as a system (110)) may include one or more processor(s) (202). The one or more processor(s) (202) may be implemented as one or more microprocessors, quantum processing units (QPUs), microcomputers, microcontrollers, edge or fog microcontrollers, digital signal processors, central processing units, logic circuitries, and/or any devices that process data based on operational instructions. Among other capabilities, the one or more processor(s) (202) may be configured to fetch and execute computer-readable instructions stored in a memory (204) of the system (110). The memory (204) may be configured to store one or more computer-readable instructions or routines in a non-transitory computer readable storage medium, which may be fetched and executed to create or share data packets over a network service. The memory (204) may comprise any non-transitory storage device including, for example, volatile memory such as Random-Access Memory (RAM), or non-volatile memory such as Electrically Erasable Programmable Read-only Memory (EPROM), flash memory, and the like.
[68] In an embodiment, the system (110) may include an interface(s) (206). The interface(s) (206) may comprise a variety of interfaces, for example, interfaces for data input and output devices, referred to as input/output (I/O) devices, storage devices, and the like. The interface(s) (206) may facilitate communication for the system (110). The interface(s) (206) may also provide a communication pathway for one or more components of the system (110). Examples of such components include, but are not limited to, processing unit/module(s) (208) and a database (210).
[69] The processing unit/module(s) (208) may be implemented as a combination of hardware and programming (for example, programmable instructions) to implement one or more functionalities of the processing module(s) (208). In examples described herein, such combinations of hardware and programming may be implemented in several different ways. For example, the programming for the processing module(s) (208) may be processor-executable instructions stored on a non-transitory machine-readable storage medium and the hardware for the processing unit(s) (208) may comprise a processing resource (for example, one or more processors), to execute such instructions. In the present examples, the machine-readable storage medium may store instructions that, when executed by the processing resource, implement the processing unit(s) (208). In such examples, the system (110) may include the machine-readable storage medium storing the instructions and the processing resource to execute the instructions, or the machine-readable storage medium may be separate but accessible to the system (110) and the processing resource. In other examples, the processing unit(s) (208) may be implemented by electronic circuitry. In an aspect, the database (210) may comprise data that may be either stored or generated as a result of functionalities implemented by any of the components of the processor (202) or the processing units (208).
[70] In an embodiment, the processing unit (208) may include one or more units/modules such as, but not limited to, a data acquisition unit (212), a quantum solver unit (214), a shortest path solver unit (216), and other unit(s) (218).
[71] Referring to FIG. 2, the database (210) may store data related to the vehicular network (100-B) as shown in FIG. 1B. The data related to the vehicular network (100-B) may include, for example, without limitations, details related to a location of the source node (114) and one or more destination nodes (1-9), the distance between the source node (114) and the destination nodes (1-9), a number of vehicles (102) in the vehicular network (100-B), a capacity of the vehicle (102), etc.
[72] In one embodiment, the one or more processor(s) (202) may enable the data acquisition unit (212) to acquire one or more data related to the vehicular network (100-B) and may provide the acquired data to the quantum solver unit (214) to compute one or more optimized routes for the one or more vehicles (102) in the vehicular network (100-B) using quantum annealing techniques. In some embodiments, the quantum annealing techniques for determining the optimized vehicle route may include, for example, without limitations, a quadratic unconstrained binary optimization (QUBO) solver or a density-based spatial clustering of applications with noise (DBSCAN) solver. Further, the obtained optimized routes may be communicated to the shortest path solver unit (216) to determine a shortest path for the vehicle (102) to traverse through.
[73] In some embodiments, the shortest path solver unit (216) may obtain a partitioning graph based on the optimized routes. The partitioning graph may include nodes representing the source node (114) and one or more destination nodes (1-9) and edges representing the route taken by the vehicle (102), wherein the number of edges is equal to the number of vehicles (102) in the vehicular network (100-B). Further, the shortest path solver unit (216) may assign a demand value to the source node (114) and the one or more destination nodes (1-9), and a weight value to the one or more edges in the partition graph and determine a shortest route from the source node (114) to the one or more destination nodes (1-9) for the vehicle (102) based on the vehicle capacity and the edge weights value in the partition graph, wherein the assigned shortest path may be communicated to the vehicle (102) through the interface (s) (206). In an example embodiment, the demand value may be an input demand at the node such as, without limitations, a number of orders to be delivered at the node.
[74] A person of ordinary skill in the art will appreciate that the exemplary block diagram (200) may be modular and flexible to accommodate any kind of changes in the system (110).
[75] In some embodiments, one or more exiting solutions for the CVRP are compared against the proposed solution. For example, the implementation of genetic algorithm, quantum annealing technique, quadratic unconstrained binary optimisation (QUBO) problem, density-based spatial clustering of applications with noise (DBSCAN) for the CVRP are compared with the currently proposed solution. The existing techniques for solving the CVRP are discussed with reference to FIGs. 3-6 as explained in detail below.
[76] FIG. 3 illustrates an exemplary flow diagram (300) of a genetic algorithm (GA) for solving the CVRP.
[77] Referring to FIG. 3, the method (300) may include at step 302, generating an initial population of chromosomes. This includes a randomization on an initial solution and the population is said be the first generation, i.e. . Further, the method (300) may include at step 304, calculating a fitness of each chromosome n of the population, . This measures the quality of the chromosome (input). The fitness , may be performed based on analyzing the feasibility of the chromosome (inputs) based on certain constraints. The method (300) may further include at step 306, creating a new generation or a new population based on selecting two parent chromosomes from the initial population according to their fitness. For example, techniques like Roulette wheel and weighted ranking approaches may be implemented for the selection and the chromosome that has a high fitness values, has a higher chance of getting selected. Upon selecting the feasibility of the selected chromosomes may be determined based on the constraints. By repeating the process of selection and feasibility analysis, a new generation of chromosomes may be obtained.
[78] Referring to FIG. 3, method (300) may further include at step 308 performing a crossover function, by taking two chromosomes and (denoted as parent chromosomes) as inputs and generate a new set of off springs (children) chromosomes such that the children chromosomes have inherited the properties from the parent chromosomes and then analyzing the feasibility of the children chromosome based on the constraints. The method (300) may further include at step 310, performing a mutation function, by taking a chromosome as input, adding random noise to the input features to generate a new chromosome. The noise may help in capturing the variability of the input space, making the method generalize and concentrate on a global solution instead of a local one. Further, the feasibility of the chromosome may be analyzed based on the constraints and the feasible children chromosomes (off springs) are added to the ‘new’ population and the newly generated population is used further in the algorithm in an iterative manner.
[79] Referring to FIG. 3, the method (300) may further include at step 312, determining if a terminating condition is satisfied. If the terminating condition is satisfied, the process ends by returning the best solution in current population. The terminating condition depends on how the average quality of the population changes with a generation. On the other hand, if the termination condition is not met, the method (300) iterates with the step 304, calculating the fitness associated with the new population.
[80] For example, the genetic algorithm may be applied to the VRP having the following constraints: eight cities and three vehicle nodes. Chromosome: vector of variables having values with city node and vehicle node below in Table 1.
5 4 3 * 1 2 8 * 6 7
Table 1
[81] Referring to the above Table 1, the ‘*’ denotes the vehicles and nodes (5, 4, 3, 1, 2, 8, 6, 7) denotes the routes. The genetic algorithm aims to minimize the overall distance with penalizing if the constraints are violated, wherein the constraint includes a vehicle capacity constraint and a heuristic includes filling * till demand fulfil is more than capacity.
[82] Further, mixed integer programming (MIP) formulation for VRP is given as follows:
The sets considered include
Sets:
1. I, J = Set of all the nodes
2. K = Set of all the vehicles
Parameters:

Decision Variables

Objective Function

Constraints

Vehicle leaves node that it enters

Ensure that every node is entered once

Every vehicle leaves depot

A node cannot enter itself after exiting itself

Sub-tour elimination constraint

[83] The above conditions result in a solution for VRP based on the genetic algorithm as may be implemented using classical processors.
[84] FIG. 4A illustrates an exemplary flow diagram (400-A) of a simulated annealing process for solving the CVRP.
[85] Simulated annealing (SA) is a probabilistic technique for approximating a global optimum of a given function. The SA process makes use of randomness as part of the search process and therefore is appropriate for nonlinear objective functions. Further, the SA is analogous to annealing in metallurgy and uses temperature and energy states for making moves in a search space. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions. This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions allows for a more extensive search for the global optimal solution. The SA algorithm may be represented using a pseudo code as given below.
Let
For through (exclusive):

Pick a random neighbor,
If :

Output: the final state
[86] The simulated annealing process involves a basic iteration step and an acceptance probability step as described below.
[87] Basic Iteration: At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in-state s. These probabilities ultimately lead the system to move to states of lower energy. Typically, this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.
[88] Acceptance probability: Accepting probability depends on difference of current energy and new energy of system and temperature. The effect is that poor solutions have more chances of being accepted early in the search and less likely of being accepted later in the search. The intent is that the high temperature at the beginning of the search will help the search locate the basin for the global optima and the low temperature later in the search will help the algorithm hone on the global optima.
[89] Referring to FIG. 4A, the simulated annealing process or SA process (400) may include at step 402, setting an initial state or solution or an initial temperature. The SA process (400) may include at step 404, determining if the termination criteria is met i.e. checking termination criteria based on lower limit of temperature and number of iterations. If the termination criteria is met, the SA process (400) may include at step 406, getting the solution. On the other hand, if the termination criteria are not met, the SA process (400) may include at step 408, selecting neighboring solution states. The SA process (400) may include at step 410, calculating an objective or the new energy state. Further, the SA process (400) may include at step 412, calculating probability of acceptance based on temperature, energy difference and checking whether the new solution is acceptable in step 414. If the new solution is acceptable, the SA process (400) may include at step 416, selecting the neighboring solution and decreasing the temperature at step 420. On the other hand, if the new solution is not accepted, the SA process (400) may include at step 418, selecting the old solution and decreasing the temperature at step 420.
[90] The SA process (400) may be applied to quantum computer resulting in a quantum annealing process. The quantum annealing process is based on the concept of adiabatic process. For example, the adiabatic process may include a process that does not involve the transfer of heat or matter into or out of a thermodynamic system. In an adiabatic process, energy is transferred to the surroundings only as work.
[91] Referring to quantum adiabatic process, first, a (potentially complicated) Hamiltonian is found whose ground state describes the solution to the problem of interest. Next, a system with a simple Hamiltonian is prepared and initialized to the ground state. Finally, the simple Hamiltonian is adiabatically evolved to the desired complicated Hamiltonian. As is known in the art, the adiabatic theorem, the system remains in the ground state, so at the end the state of the system describes the solution to the problem. Also, adiabatic quantum computing has been shown to be polynomial equivalent to conventional quantum computing in the circuit model.
[92] For example, for a quantum processor, the Hamiltonian may be represented as

The Hamiltonian is the sum of two terms, the initial Hamiltonian and the final Hamiltonian:
[93] Initial Hamiltonian (first term) - The lowest-energy state of the initial Hamiltonian is when all qubits are in a superposition state of 0 and 1. This term is also called the tunnelling Hamiltonian.
[94] Final Hamiltonian (second term) - The lowest-energy state of the final Hamiltonian is the answer to the problem that is being tried to solve. The final state is a classical state and includes the qubit biases and the couplings between qubits. This term is also called the problem Hamiltonian.
[95] The quantum annealing process also uses an Ising model of ferromagnetism traditionally used in statistical mechanics. In the Ising model variables are “spin up” (?) and “spin down” (?), states that correspond to +1 and -1 values (atomic “spins” or magnetic dipole moments). Relationships between the spins, represented by couplings, are correlations or anti-correlations. The objective function (Hamiltonian) expressed as an Ising model is as follows:

where the linear coefficients corresponding to qubit biases are hi, and the quadratic coefficients corresponding to coupling strengths are .
[96] Referring to quantum annealing technique, the quantum annealing simply uses quantum physics to find low-energy states of a problem and therefore the optimal or near-optimal combination of elements.
[97] As is known in general, the quantum annealing - starts from a quantum-mechanical superposition of all possible states (candidate states) with equal weights. Then the system evolves following the time-dependent Schrödinger equation, a natural quantum-mechanical evolution of physical systems. The amplitudes of all candidate states keep changing, realizing a quantum parallelism, according to the time-dependent strength of the transverse field, which causes quantum tunnelling between states as shown in FIG. 4B discussed in detail below. If the rate of change of the transverse-field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian (adiabatic quantum computation). If the rate of change of the transverse-field is accelerated, the system may leave the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final problem Hamiltonian, i.e., adiabatic quantum computation. The transverse field is finally switched off, and the system is expected to have reached the ground state of the classical Ising model that corresponds to the solution to the original optimization problem.
[98] FIG. 4B illustrates a quantum tunnelling mechanism (400-B) associated with a quantum annealing process.
[99] Referring to FIG. 4B, the quantum tunnelling mechanism provides optimizing a cost function for a computationally hard problem like minimum travel distance for the TSP. The quantum tunnelling mechanism provides getting out of a shallower local minimum like the configuration C (travel route), to reach a deeper minimum C'. In general, a jump over the energy or the cost barriers in a classical optimization method may be achieved by tunnelling quantum mechanically.
[100] FIG. 4C illustrates an energy diagram (400-C) associated with the quantum annealing process.
[101] Referring to FIG. 4C, the states associated with quantum bits or qubits in the quantum processing unit (QPU) during the quantum annealing process is shown.
[102] The quantum bits—also known as qubits—are the lowest energy states of the superconducting loops that make up the QPU. These states have a circulating current and a corresponding magnetic field. As with classical bits, a qubit can be in state of 0 or 1. Further, because the qubit is a quantum object, it can also be in a superposition of the 0 state and the 1 state at the same time. At the end of the quantum annealing process, each qubit collapses from a superposition state into either 0 or 1 (a classical state).
[103] Referring to FIG. 4C, there is just one valley (a), with a single minimum. With the running of the quantum annealing process, the barrier is raised, and this turns the energy diagram into what is known as a double-well potential (b). Here, the low point of the left valley corresponds to the 0 state, and the low point of the right valley corresponds to the 1 state. The qubit ends up in one of these valleys at the end of the anneal. Further, with everything else being equal, the probability of the qubit ending in the 0 or the 1 state is equal (50 percent). We can, however, control the probability of it falling into the 0 or the 1 state by applying an external magnetic field to the qubit (c). This field tilts the double-well potential, increasing the probability of the qubit ending up in the lower well. The programmable quantity that controls the external magnetic field is called a bias, and the qubit minimizes its energy in the presence of the bias. The application of bias may be used for optimizing the given problem using the QPU.
[104] FIG. 5 illustrates a flow diagram (500) associated with a quadratic unconstrained binary optimization (QUBO) formulation for solving a CVRP.
[105] Referring to FIG. 5, the method (500) for solving CVRP using QUBO problem may include at step 502, formulating a quadratic program for the given problem, for example, without limitations, CVRP. The method (500) may further include at step 504, converting the quadratic program to QUBO. In general, QUBO problems are traditionally used in computer science with variables set as TRUE and FALSE, with states that correspond to 1 and 0 values. A QUBO problem is defined using an upper-diagonal matrix Q, which is an upper-triangular matrix of real weights, and , a vector of binary variables, as minimizing the function:

where the diagonal terms are the linear coefficients and the nonzero off-diagonal terms are the quadratic coefficients . This can be expressed more concisely as:

[106] Referring to FIG. 5, the method (500) may further include at step 506 embedding the QUBO into the QPU. Further, the method (500) may include at step 508, running an annealing procedure on the CVRP converted to QUBO. The method (500) may include at step 510, obtaining the sample results. QUBO implemented on the QPU subjected to annealing results in a full QUBO quantum solver for the VRP. In the absence of noise, the solution obtained is the optimal solution. The following parameters are defined for the full QUBO solver.
- identifiers of vehicles

- identifiers of nodes (0 - depot)

Let ? Binary Variable that is if the vehicle is in the node at the location on the route (and otherwise)

- cost of travel from node to node (for ),

Objective function

Constraints:
Every node, other than the depot is served at exactly one time-step by exactly one vehicle

A vehicle can only be at one node at any given time-step

Final QUBO:

Where, are penalty parameters, usually set to high values.

[107] The major advantage of FQS is that it does not involve any form of approximation. That is, the solution is optimal if the QPU used to solve it is ideal and noiseless. The major disadvantage is that FQS has a high qubit complexity. In particular, it requires up to qubits.
[108] In some embodiments, the FQS may be implemented to solve the travelling salesman problem (TSP) associated with various routes that may be taken by the vehicle (102) as shown in FIG. 1B.
[109] FIG. 6 illustrates a flow diagram (600) of a density-based spatial clustering of applications with noise (DBSCAN) algorithm for obtaining vehicle routes.
[110] Referring to FIG. 6, the method (600) may include at step 602, building ‘k’ clusters using the DBSCAN algorithm, wherein ‘k’ clusters may be determined based on at least one of the capacity of the vehicle (102) and a time constraint associated with the vehicle (102). Each cluster may include a set of destination nodes from the one more destination nodes. The method (600) may further include at step 604, assigning each cluster to each vehicle (102) as shown in FIG. 1A. In some embodiments, each cluster may be assigned to a particular vehicle randomly. In an example embodiment, the cluster assigned may include the set of destination nodes the vehicle (102) may deliver the order, wherein the vehicle (102) traverses through each node in the cluster. Further, the method (600) may include at step 606, solving TSP for each vehicle using quantum annealing. The method (600) includes obtaining, sample vehicle routes based on applying the TSP for each vehicle.
[111] The above method (600) for solving the CVRP may be effective when there are lesser nodes and lesser vehicles in the vehicular network. However, as the number of nodes and vehicles increases, the method (600) fails.
[112] Another known method for obtaining optimized routes is solution partitioning solver (SPS). In this method, the TSP solution found by another algorithm, for example, FQS, is divided into consecutive intervals to obtain the solution for the CVRP.
[113] For example, let be the TSP solution for orders, let be a capacity of the vehicle , let be the sum of weights of orders (in the order corresponding to TSP solution) and let be the total cost of serving only orders . Also, let be the cost of the best solution for orders and for the set of vehicles . Now, the dynamic programming formula using the SPS for solving the CVRP is given by:

where and for

1. Consider a sequence of vehicles and attach these to deliveries in a set of orders. For example, a first set of orders may be assigned to vehicle 1 and a second set of orders may be assigned to , etc.

2. Now, the dynamic programming formula is given by:

3. To count this dynamic effectively, it is observed that:

[114] The SPS further involves selecting some random permutations of vehicles and perform dynamic programming for each of them to assign the optimized route. For example, without limitations, the dynamic programming may be used to determine the optimized route for each vehicle and an associated cluster.
[115] Referring to the above discussion with respect to existing methods for solving the CVRP, the SPS implemented on the QPU exhibits best performance with respect to solution accuracy, and a comparable qubit complexity with respect to other algorithms. The Solution Partitioning Solver however relies on the successful partitioning of the TSP solution and may get stuck if such a partition is not possible within the given capacity limit.
[116] Therefore, to over come the limitations of the existing methods for solving the CVRP, a hybrid approach is discussed in the present disclosure.
[117] In some embodiments, a hybrid algorithm combining quantum approach with a classical algorithm, for example, without limitations, a recursive DBSCAN algorithm, is implemented to solve the CVRP. The recursive DBSCAN may be used as clustering algorithm with limited size of clusters and the TSP may be solved using FQS separately (by assume the number of vehicles equal to 1). In some embodiments, if the number of clusters is equal to (or lower than) the number of vehicles in the vehicular network, the solution to the CVRP may be obtained immediately. For example, without limitation, each cluster may be assigned to one vehicle. Otherwise, the FQS runs recursively considering clusters as deliveries, so that each cluster contains orders which in the final result are served one after another without leaving the cluster. For example, without limitations, some of the vehicles in the plurality of vehicles may be assigned one or more cluster such that they may traverse one cluster and then move to another cluster.
[118] In some embodiments, the hybrid algorithm combines the TSP solved using a quantum solver algorithm with a shortest path solver to obtain the best route for the vehicle (102) of FIG. 1B. In an embodiment, the Shortest Path Solver is able to relax the constraint on the number of vehicles and provides a solution regardless of the number of vehicles i.e., the Shortest Path Solver may handle fixed number of vehicles, as well as optimize over the number of vehicles as a parameter, which the Solution Partitioning Solver cannot handle.
[119] In another embodiment, the Shortest Path Solver algorithm provides optimal partitioning of the given TSP solution obtained based on any of the quantum annealing techniques discussed above, thus providing better partitioning of the routes compared to the Solution Partitioning Solver.
[120] FIG. 7A illustrates a flow diagram (700-A) for determining vehicle route, in accordance with an embodiment of the present disclosure.
[121] Referring to FIG. 7A, the method (700-A) may include at step 702, solving the TSP for a given set of nodes i.e., the number source and destination nodes in the vehicular network (100-B) as shown in FIG. 1B, using a quantum annealing process. In some embodiments, the quantum annealing process may include at least one of quadratic unconstrained binary optimization (QUBO) solver or a density-based spatial clustering of applications with noise (DBSCAN) solver to obtain the TSP solution. The TSP solution provides a set of optimized routes for a vehicle from the source node to one or more target nodes, such that each node is traversed once. The method (700-A) may further include at step 704, partitioning the routes obtained into k-sections. In an embodiment, the partitioning may be done based on the shortest path solver and is discussed in detail below with reference to FIG. 7B.
[122] Referring to FIG. 7A, the method (700-A) further includes assigning each of the k-sections to the one or more vehicles (102) in the vehicular network (100-B) of FIG. 1B.
[123] FIG. 7B illustrates a flow diagram (700-B) for finding a shortest path in a partition graph, in accordance with an embodiment of the present disclosure.
[124] Referring to FIG. 7B, the method (700-B) may include at step 708, building a partitioning graph based on the one or more optimized routes obtained based on solving the TSP using quantum annealing techniques, as discussed above. In some embodiments, the graph may include the source point or the depot from where the vehicle (102) may start and one or more destination points or delivery points where the vehicle (102) may deliver the items as its nodes and the route taken by the vehicle as the edges. In one embodiment, the number of edges is selected to be equal to the number of vehicles in the vehicular network. The method (700-B) may further include at step 710, finding a shortest path on the partitioned graph based on assigning a demand value to the source node and destination nodes, and a weight value to the edges in the partition graph. In an example embodiment, the demand may be the set of orders associated with a last mile delivery and may be user defined.
[125] The partitioning of the graph and determining the shortest path are explained in detail below with reference to FIGs. 8A-8D.
[126] FIG. 8A illustrates a graph representation (800-A) of vehicle routes obtained by applying a travelling salesman problem (TSP) to the number of vehicles in the network (100), in accordance with an embodiment of the present disclosure.
[127] Referring to FIG. 8A, the graph (800-A) representing the optimized routes obtained based on applying a quantum annealing solution for the TSP problem. The graph (800-A) includes a set of nodes 0-8 representing the source and destination nodes associated with the route taken by the vehicle and the edges represent the route travelled by the vehicle. Each node is assigned with a demand value and the edges are assigned an edge weight value. In some embodiments, a partitioning graph may be constructed based on the demand and edge values and then a shortest path is determined on the constructed partitioning graph.
[128] FIG. 8B illustrates a partitioning graph (800-B) formed based on the vehicle routes obtained using TSP, in accordance with an embodiment of the present disclosure.
[129] Referring to FIG. 8B, the graph (800-B) is the partitioning graph obtained from the graph (800-A) representing the TSP solution. In some embodiments, the partitioning graph (800-B) may be constructed by implementing the following steps:
For each pair where in the TSP order (TSP sequence):

1. Let be the sum of demands for nodes from to in the TSP order including and excluding (i.e., in )

2. There is an edge in the Partitioning graph if (Vehicle Capacity)

3. The weight of edge is the cost of the vehicle delivering all nodes including and excluding (i.e., in )

[130] FIG. 8C illustrates a shortest path (800-C) obtained on the partitioning graph, in accordance with an embodiment of the present disclosure.
[131] Referring to FIG. 8C, the shortest path (800-C) may be obtained on the portioning graph based on applying a variation of the Bellman-Ford algorithm on the partitioning graph (800-B) using at most edges (m is the number of vehicles). The shortest path may be obtained by defining a function which is the length of the shortest path on the auxiliary graph or the partitioning graph (800-B) from a source to a target using at most edges, wherein the source (s) will be the first node in the TSP route, and target (t) will be the depot node.

[132] In one embodiment, the shortest path may be obtained by memoization / dynamic programming. In another embodiment, Djikstra’s algorithm may be used to determine shortest path, when unable to find shortest path with at most edges.
[133] Referring to FIG. 8C, in an example embodiment, three shortest paths associated with three vehicles are estimated with edge weight 11, 13, and 20. The three shortest paths may be assigned to any three vehicles to travel from the source node to the destination node.
[134] FIG. 8D illustrates vehicle routes (800-D) determined based on the shortest path, in accordance with an embodiment of the present disclosure.
[135] Referring to FIG. 8D, the three shortest paths determined above in FIG. 8C may be assigned to three vehicles, for example, without limitations vehicles (102-1, 102-2, 102-3) as their final route. By way of example, without limitations, the vehicle (102-1) may be assigned a first route from the source node (0) to the destination nodes (2, 4) and back to the source node (0). Similarly, the vehicle (102-2) may be assigned a second route from the source node (0) to the destination nodes (6,1) and back to the source node (0) and the vehicle (102-3) may be assigned a third route from the source node (0) to the destination nodes (7, 5, 3) and back to the source node (0).
[136] In an embodiment, the existing techniques for solving the CVRP is compared with the proposed technique under various scenarios. A first comparison is made based on a qubit complexity associated with all the existing techniques and the proposed method and a second comparison is made based on applying the existing techniques and the proposed method to different vehicular networks.
[137] The first comparison made based on qubit Complexity i.e., the number of qubits required to solve a particular instance of a problem is shown below in Table 2. The qubit complexity of some of the mentioned quantum solvers is shown in the Table 2 below.

Solver Name Worst Case Complexity
Full QUBO Solver
DBSCAN Solver
Solution Partitioning Solver
Shortest Path Solver
Table 2

[138] Referring to the above table, FQS is an exact solver (i.e., in the absence of noise it will provide an optimal solution) but has a poor worst-case complexity. The other three are heuristic solvers.
[139] The second performance comparison is made on different experimental scenarios and a real data scenario. For example, a first experiment for the CVRP contained 10 Nodes and 3 vehicles, while a second experiment had 15 Nodes and 5 vehicles. Similarly, the 3rd and 4th experiment had a larger number of nodes and vehicles. The last experiment was done on real data of existing scenario where 45 nodes and 31 vehicles were used, i.e.,
Experiment 1: E1 with capacity, homogenous (10 Nodes, 3 vehicles)
Experiment 2: E2 with capacity, homogenous (15 Nodes, 5 vehicles)
Experiment 3: E3 with capacity, homogenous (25 Nodes, 9 vehicles)
Experiment 4: E4 with capacity, homogenous (50 Nodes, 21 vehicles)
Real Data (45 Nodes, 31 vehicles) scenario.
[140] The results of the comparison is shown below in Table 3.
Cost -> E1 (10 Nodes, 3 vehicles) E2 (15 Nodes, 5 vehicles) E3 (25 Nodes, 9 vehicles) E4 (50 Nodes, 21 vehicles) Real Data (45 Nodes, 31 vehicles)
Simulated annealing algorithm 167 487 346 666 ~ 72 lakh
Genetic Algorithm 167 491 396 720 ~ 72 lakh
DBSCAN in QPU 171 665 538 Unable to solve Unable to solve
Solution Partitioning Solver
(D-Wave Hybrid) Unable to solve 559 502 840 ~ 78 lakh
Solution Partitioning Solver (with QBSolv) Unable to solve 520 547 860 ~ 80 lakh
Shortest Path Solver (D-Wave Hybrid) 149 (with fleet extension) 557 (with fleet extension) 426 843 ~ 85 lakh
Shortest Path Solver (with QBSolv) 149 (with fleet extension) 520 547 860 ~ 80 lakh
Table 3
[141] From the above table, Table 3, it may be understood that the quantum based approaches and classical approaches give comparable results for smaller use-cases, but in larger use-cases the classical approaches do better due to noise, connectivity, and qubit limitations in the existing QPU. The hardware limitations in the QPU may be reduced by implementing the proposed hybrid technique for the VRP.
[142] A person of ordinary skill in the art will appreciate that these are mere examples, and in no way, limit the scope of the present disclosure.
[143] FIG. 9 illustrates an exemplary computer system (900) in which or with which embodiments of the present disclosure may be utilized. As shown in FIG. 9, the computer system (900) may include an external storage device (910), a bus (920), a main memory (930), a read-only memory (940), a mass storage device (950), communication port(s) (960), and a processor (970). A person skilled in the art will appreciate that the computer system (900) may include more than one processor and communication ports. The processor (970) may include various modules associated with embodiments of the present disclosure. The communication port(s) (960) may be any of an RS-232 port for use with a modem-based dialup connection, a 10/100 Ethernet port, a Gigabit or 10 Gigabit port using copper or fibre, a serial port, a parallel port, or other existing or future ports. The communication port(s) (960) may be chosen depending on a network, such a Local Area Network (LAN), Wide Area Network (WAN), or any network to which the computer system (900) connects. The main memory (930) may be random access memory (RAM), or any other dynamic storage device commonly known in the art. The read-only memory (940) may be any static storage device(s) including, but not limited to, a Programmable Read Only Memory (PROM) chips for storing static information e.g., start-up or basic input/output system (BIOS) instructions for the processor (970). The mass storage device (950) may be any current or future mass storage solution, which may be used to store information and/or instructions.
[144] The bus (920) communicatively couples the processor (970) with the other memory, storage, and communication blocks. The bus (920) can be, e.g. a Peripheral Component Interconnect (PCI) / PCI Extended (PCI-X) bus, Small Computer System Interface (SCSI), universal serial bus (USB), or the like, for connecting expansion cards, drives, and other subsystems as well as other buses, such a front side bus (FSB), which connects the processor (970) to the computer system (900).
[145] Optionally, operator and administrative interfaces, e.g. a display, keyboard, and a cursor control device, may also be coupled to the bus (920) to support direct operator interaction with the computer system (900). Other operator and administrative interfaces may be provided through network connections connected through the communication port(s) (960). In no way should the aforementioned exemplary computer system (900) limit the scope of the present disclosure.
[146] While considerable emphasis has been placed herein on the preferred embodiments, it will be appreciated that many embodiments can be made and that many changes can be made in the preferred embodiments without departing from the principles of the disclosure. These and other changes in the preferred embodiments of the disclosure will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter to be implemented merely as illustrative of the disclosure and not as limitation.

ADVANTAGES OF THE PRESENT DISCLOSURE
[147] The present disclosure provides last mile delivery optimization of retail using a Quantum based method.
[148] The present disclosure provides a custom formulation of capacitated Vehicle Routing Problem (VRP) using hybrid classical-quantum approach.
[149] The present disclosure provides optimal partitioning of a travelling salesman problem (TSP) solution.
[150] The present disclosure accommodates fleet extension in case the VRP is not being solved with the original number of vehicles.
[151] The Shortest Path Solver algorithm guarantees an optimal partitioning of a given TSP solution, given that the quantum hardware is able to find a good TSP solution.

,CLAIMS:1. A system (110) for solving capacitated vehicle routing problem (CVRP) in a vehicular network (100-B), said system comprising:
one or more processors (202); and
a memory (204) operatively coupled to the one or more processors (204), wherein the memory (204) comprises processor-executable instructions, which on execution, cause the one or more processors (202) to:
obtain one or more optimized routes, from a source node (114) to one or more destination nodes (1-9), for at least one vehicle (102) of a plurality of vehicles in the vehicular network (100-B), wherein the one or more destination nodes (1-9) are traversed one time by the at least one vehicle (102);
create a partition graph (800-B), comprising the source node, the one or more destination nodes, and one or more edges between the source node and the one or more destination nodes, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network (100-B);
assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph (800-B); and
determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle and the weight values assigned in the partition graph (800-B).

2. The system (110) as claimed in claim 1, wherein the memory (204) comprises processor-executable instructions, which on execution, cause the one or more processors (202) to:
assign the determined shortest route to the at least one vehicle (102) of the plurality of vehicles in the vehicular network.

3. The system (110) as claimed in claim 1, wherein the source node comprises a starting point for the at least one vehicle (102), the one or more destination nodes comprise one or more delivery stops for the at least one vehicle (102), and the one or more edges comprise a route traversed by the at least one vehicle (102) from the source node to the one or more destination nodes.

4. The system (110) as claimed in claim 1, wherein the number of edges in the partition graph (800-B) is equal to a number of the plurality of vehicles in the vehicular network (100-B).

5. The system (110) as claimed in claim 1, wherein the memory (204) comprises processor-executable instructions, which on execution, cause the one or more processors (202) to:
create a plurality of clusters based on at least one of the capacity of the vehicle (102) and a time constraint associated with the vehicle (102);
assign at least one cluster of the plurality of clusters to the at least one vehicle; and
determine the one or more optimized routes for the at least one vehicle based on the assignment of the at least one cluster and quantum annealing techniques.

6. A method for solving capacitated vehicle routing problem (CVRP) in a vehicular network (100-B), comprising:
obtaining, by one or more processors (202) associated with a system (110), one or more optimized routes, from a source node (114) to one or more destination nodes (1-9), for at least one vehicle (102) of a plurality of vehicles in the vehicular network (100-B), wherein the one or more destination nodes (1-9) are traversed one time by the at least one vehicle;
creating, by the one or more processors (202), a partition graph (800-B), comprising the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network;
assigning, by the one or more processors (202), a demand value to the source node and the one or more destination nodes, and a weight value to the one or mode edges in the partition graph (800-B); and
determining, by the one or more processors (202), a shortest route from the source node to the one or more destination nodes for the at least one vehicle (102) based on at least one of a capacity of the vehicle and the weight value assigned in the partition graph (800-B).

7. The method as claimed in claim 6, comprising:
assigning, by the one or more processors (202), the determined shortest route to the at least one vehicle (102) of the plurality of vehicles in the vehicular network (100-B).

8. The method as claimed in claim 6, wherein the source node comprises a starting point for the at least one vehicle (102), the one or more destination nodes comprise one or more delivery stops for the at least one vehicle (102), and the one or more edges comprise a route traversed by the at least one vehicle from the source node to the one or more destination nodes.

9. The method as claimed in claim 6, wherein the number of edges in the partition graph is equal to a number of the plurality of vehicles in the vehicular network.

10. The method as claimed in claim 6, comprising:
creating, by the one or more processors (202), a plurality of clusters based on at least one of the capacity of the vehicle (102) and a time constraint associated with the vehicle (102); and
assigning, by the one or more processors (202), at least one cluster of the plurality of clusters to the at least one vehicle; and
determining, by the one or more processors (202), the one or more optimized routes for the at least one vehicle (102) based on the assignment of the at least one cluster and quantum annealing techniques.

11. A user equipment (UE), comprising:
a processor communicatively coupled to a system (110);
the system (110) comprising one or more processors (202) operatively couple to a memory (204) comprising processor-executable instructions, which on execution, cause the one or more processors (202) to:
obtain one or more optimized routes, from a source node (114) to one or more destination nodes (1-9), for at least one vehicle (102) of a plurality of vehicles in a vehicular network (100-B), wherein the one or more destination nodes are traversed one time by the at least one vehicle;
create a partition graph (800-B), comprising the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph is associated with the plurality of vehicles in the vehicular network;
assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph (800-B); and
determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle (102) and the weight value assigned in the partition graph (800-B).
12. A non-transitory computer readable medium that comprises one or more instructions stored thereupon that when executed by a processor causes the processor to
obtain one or more optimized routes, from a source node (114) to one or more destination nodes (1-9), for at least one vehicle (102) of a plurality of vehicles in a vehicular network (100-B), wherein the one or more destination nodes are traversed one time by the at least one vehicle;
create a partition graph (800-B), comprising the source node, the one or more destination nodes, and one or more edges, based on the one or more optimized routes, wherein the number of edges in the partition graph (800-B) is associated with the plurality of vehicles in the vehicular network (110-B);
assign a demand value to the source node and the one or more destination nodes, and a weight value to the one or more edges in the partition graph (800-B); and
determine a shortest route from the source node to the one or more destination nodes for the at least one vehicle based on at least one of a capacity of the vehicle (102) and the weight value assigned in the partition graph (800-B).