SYSTEMS AND METHODS FOR MULTI-LEVEL COMBINATORIAL RESOURCE OPTIMIZATION

Systems and methods for optimizing delivery vehicle resources (e.g. a plurality of vehicles) are described herein. Available time slots for the plurality of vehicles are determined and presented to a user. In response to receiving a delivery order indicating a selected time slot, the delivery order is assigned to a vehicle from the plurality of vehicles based on a time slot indicated in the delivery order and a set of delivery parameters. A delivery route is calculated for each vehicle having a delivery order based on the set of delivery parameters. An optimized delivery route is calculated for each vehicle having a delivery order based on the set of delivery parameters.

TECHNICAL FIELD

This application relates generally to combinatorial resource optimization, and more particularly, relates to optimizing delivery routes in a goods delivery system.

BACKGROUND

At least some known systems and industries provide delivery services to their customers. For example, some industries provide the delivery of goods, such as grocery items, to their customers, which has increasingly become a method by which consumers obtain their grocery needs. For grocery delivery services, the use of delivery vehicle resources can be optimized in order to achieve an efficient and profitable grocery delivery service. One particular optimization solution or system is resource optimization and vehicle routing (ROVR), which is designed to optimize grocery delivery routes based on a number of factors in order to make efficient use of delivery vehicle resources.

However, current solutions, including ROVR cannot scale to handle large order sizes (e.g., 2000 or more orders per day). As the number of delivery orders increases, the combinatorial space to be explored (i.e., the complexity of the optimization problem) increases exponentially. For example, doubling the number of orders may result in an exponential increase in the number of alternative delivery routes that are explored and/or considered. In addition, computational resources become bottlenecked, as the time required to optimize delivery routes increases once the number of orders becomes larger. For example, a single optimization can take longer than three minutes, which may significantly affect an optimization system's ability to allocate computation resources to other stores among a collection of hundreds of stores.

SUMMARY OF THE INVENTION

The embodiments described herein enable the optimization of vehicle resources during delivery of goods, such as grocery items. For example, in one embodiment, a system for optimizing vehicle resources during delivery of goods is disclosed. The system may include a computing device configured to communicate with a vehicle server, wherein the vehicle server is configured to communicatively couple to a plurality of vehicles. The computing device may be configured to receive, from the vehicle server, time data of the plurality of vehicles, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries and determine at least one available time slot among the plurality of time slots and communicate the at least one available time slot to at least one user terminal. The computing device may be configured to receive, from the at least one user terminal, at least one delivery order indicating at least one selected time slot from the at least one available time slot. In response to receiving the at least one delivery order indicating the at least one selected time slot, the computing device may further be configured to assign the delivery order to a vehicle from the plurality of vehicles based, at least in part, on the selected time indicated in the at least one delivery order and at least one parameter for each of the plurality of vehicles. The computing device may be configured to calculate, for the assigned vehicle, an optimized delivery route based, at least in part, on the at least one delivery parameter and transmit the optimized delivery route to the assigned vehicle.

In other embodiments, a method for optimizing vehicle resources during delivery of goods is disclosed. Time data of a plurality of vehicles may be received from a vehicle server, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries and at least one available time slot among the plurality of time slots is determined and communicated to at least one user terminal. At least one delivery order indicating at least one selected time slot may be received from the user terminal. In response to receiving the at least one delivery order indicating the at least one selected time slot, the delivery order may be assigned to a vehicle from the plurality of vehicles based, at least in part, on the selected time indicated in the at least one delivery order and at least one parameter for each of the plurality of vehicles. An optimized delivery route for the assigned vehicle may be calculated, based, at least in part, on the at least one delivery parameter and transmitted to the assigned vehicle.

In yet other embodiments, a non-transitory computer readable medium is disclosed, having instructions stored thereon for optimizing vehicle resources during delivery of goods. The instructions, when executed by a processor, cause a device to perform operations for such optimization. The device may communicate with a vehicle server, wherein the vehicle server is configured to communicatively couple to a plurality of vehicles. The device may receive, from the vehicle server, time data of the plurality of vehicles, wherein the time data includes a plurality of time slots for each of the plurality of vehicles that are used for a plurality of deliveries and determine at least one available time slot among the plurality of time slots and communicate the at least one available time slot to at least one user terminal. The device receive, from the at least one user terminal, at least one delivery order indicating at least one selected time slot from the at least one available time slot. In response to receiving the at least one delivery order indicating the at least one selected time slot, the device may assign the delivery order to a vehicle from the plurality of vehicles based, at least in part, on the selected time indicated in the at least one delivery order and at least one parameter for each of the plurality of vehicles. The device may calculate, for the assigned vehicle, an optimized delivery route based, at least in part, on the at least one delivery parameter and transmit the optimized delivery route to the assigned vehicle.

In some embodiments, a computing device is configured to communicate with a user terminal, a first vehicle server, and a second vehicle server. The first vehicle server may communicate with a first plurality of vehicles that execute (e.g., deliver or pickup) orders in a first geographical area. The second vehicle server may communicate with a second plurality of vehicles that execute orders in a second geographical area. The first geographical area and second geographical area can be different.

The computing device may receive, from the first vehicle server, first shift data for the first plurality of vehicles. First shift data may include a plurality of first time periods, where each first time period corresponds to a window of time that a vehicle of the first plurality of vehicles is available for execution of orders in the first geographical area. The computing device may also receive, from the second vehicle server, second shift data for the second plurality of vehicles. Second shift data includes a plurality of second time periods, where each second time period corresponds to a window of time that a vehicle of the second plurality of vehicles is available for execution of orders in the second geographical area. The computing device may receive, from the user terminal, a selected time slot for a requested order at a requested order location in the second geographical area.

The computing device may then determine a second time period of the plurality of second time periods that at least partially coincides in time with the selected time slot. The computing device may also determine a first time period of the plurality of first time periods based on a start time of the determined second time period.

The computing device may transmit, to the first vehicle server, a first order assignment for the requested order from a pick-up location in the first geographical area to a drop-off location in the second geographical area during the determined first time period. The computing device may transmit, to the second vehicle server, a second order assignment for the requested order from the drop-off location in the second geographical area to the requested order location in the second geographical area during the determined second time period.

In some embodiments, a method includes receiving, from a first vehicle server, first shift data for a first plurality of vehicles. The first shift data may include a plurality of first time periods, where each first time period corresponds to a window of time that a vehicle of the first plurality of vehicles is available for execution of orders in a first geographical area. The method may also include receiving, from a second vehicle server, second shift data for a second plurality of vehicles. The second shift data may include a plurality of second time periods, where each second time period corresponds to a window of time that a vehicle of the second plurality of vehicles is available for execution of orders in the second geographical area.

The method may also include receiving, from a user terminal, a selected time slot for a requested order at a requested order location in the second geographical area. The method may further include determining a second time period of the plurality of second time periods that at least partially coincides in time with the selected time slot, and determining a first time period of the plurality of first time periods based on a start time of the determined second time period.

The method may further include transmitting, to a first vehicle server, a first order assignment for the requested order from a pick-up location in the first geographical area to a drop-off location in the second geographical area during the determined first time period, and transmitting, to a second vehicle server, a second order assignment for the requested order from the drop-off location in the second geographical area to the requested order location in the second geographical area during the determined second time period,

In yet other embodiments, a non-transitory computer readable medium has instructions stored thereon, where the instructions, when executed by at least one processor, cause a device to perform operations that include receiving, from a first vehicle server, first shift data for a first plurality of vehicles. The first shift data includes a plurality of first time periods, where each first time period corresponds to a window of time that a vehicle of the first plurality of vehicles is available for execution of orders in a first geographical area. The operations may also include receiving, from a second vehicle server, second shift data for a second plurality of vehicles. The second shift data includes a plurality of second time periods, where each second time period corresponds to a window of time that a vehicle of the second plurality of vehicles is available for execution of orders in the second geographical area. The operations may further include receiving, from a user terminal, a selected time slot for a requested order at a requested order location in the second geographical area.

The operations may also include determining a second time period of the plurality of second time periods based on the second time period coinciding in time with the selected time slot, and determining a first time period of the plurality of first time periods based on a start time of the determined second time period. The operations may further include transmitting, to the first vehicle server, a first order assignment for the requested order from a pick-up location in the first geographical area to a drop-off location in the second geographical area during the determined first time period, and transmitting, to the second vehicle server, a second order assignment for the requested order from the drop-off location in the second geographical area to the requested order location in the second geographical area during the determined second time period.

DETAILED DESCRIPTION

As discussed above, existing solutions or systems for resource optimization cannot scale to handle large numbers of orders and do not enable sufficient flexibility with computational resources. The embodiments described herein facilitate the efficient optimization of resources in large-scale delivery systems. The embodiments described herein include, for example, the estimation of a number of available time windows for a delivery, and the presenting of available time windows to a user. The embodiments also include the determination of delivery routes for one or more vehicles and the subsequent optimization of the determined delivery routes. Although the embodiments described herein illustrate delivery resource optimization systems and methods used for the delivery of grocery goods or items, the embodiments discussed herein are not limited to such systems and methods and one of ordinary skill in the art will appreciate that the current disclosure may be used in connection with any type of system or method that addresses various different types of combinatorial optimization problems.

FIG. 1Aillustrates a system100in accordance with exemplary embodiments of the present disclosure. System100may be utilized, for example, in optimizing the use of a plurality of vehicles (not shown) in delivering groceries to users. System100may include a server105, one or more user terminals, such as terminals120,125, and130, and a vehicle server128, that are each coupled to server105. System100may further include vehicles128a-cwhich are each communicatively coupled to vehicle server128and may receive delivery order assignments and delivery routes from server105via the vehicle server128. It should be noted that, as used herein, the term “couple” is not limited to a direct mechanical, communicative, and/or an electrical connection between components, but may also include an indirect mechanical, communicative, and/or electrical connection between two or more components or a coupling that is operative through intermediate elements or spaces.

Server105, user terminals120,125, and130, and vehicle server128can each be a computing device that can be, for example, a desktop computer, laptop, mobile device, tablet, thin client, or other device having a communications interface (not shown) that can communicate with other components of system100, as explained in more detail below with respect toFIG. 1B.

In some embodiments, server105can be associated with, for example, a retail store, such as a grocery store. For example, server105can include information about the grocery items that are available from the retail store. For example, server105can maintain a database (such as database160shown inFIG. 1B) that includes details on the various grocery items available from the retail store, the quantity of each item available from the retail store, the price of each item, and (if applicable) an amount of time before a particular grocery item will perish after leaving the store (e.g. milk or fresh fruits). As will be discussed in further detail with respect toFIG. 2, server105may also maintain a database of vehicle availability which it may use to determine available time slots from the plurality of vehicles for presentation to a user (e.g. via user terminals120,125, and130).

In some embodiments, vehicle server128may enable communication between server105and each of the vehicles128a-c. For example, as server105determines delivery order assignments and delivery routes (as discussed in more detail below), server105may communicate these assignments and routes to vehicle server128, which may in turn communicate the assignments and routes to the corresponding vehicle. Vehicle server128may also transmit to server105, information regarding the plurality of time slots each of the vehicles in the plurality of vehicles has. For example, vehicle server128may transmit information regarding the number of time slots a vehicle has per delivery route, the length of each time slot, and other pertinent information regarding the plurality of time slots each vehicle has. In some embodiments, the functions of the vehicle server128may be performed by server105.

In some embodiments, each user terminal120,125, and130, can be accessed by a user to enable the user to communicate with server105. For example, each user terminal120,125, and130can be capable of connecting to, for example, the internet and communicating with server105via network135. The user can use terminals120,125, and130for accessing information from server105. For example, the user can obtain information, such as the grocery items that are available for purchase and available delivery time slots, as discussed in more detail herein.

During operation, as explained in more detail below with respect toFIGS. 1A, 2, 3A, 3B, 4A, 4B, and 5, system100can be used to facilitate the efficient delivery of goods, such as grocery items. For example, server105may receive delivery orders from user terminals120-130via network135. Such orders may be received from a variety of locations. As discussed above, although discussed in terms of grocery delivery, the embodiments described herein may be utilized to solve any combinatorial optimization problem. Upon receiving a delivery order from any of user terminals120-130, server105may assign the delivery order to an appropriate vehicle among the plurality of vehicles128a-cand determine an appropriate delivery route for that vehicle based on one or more delivery parameters. Server105may transmit the assignment and route information to the appropriate delivery vehicle via vehicle server128.

FIG. 1Bis a block diagram of an exemplary computing device110, which may be used to implement one or more of server105, user terminals120,125, and130, and vehicle server128(shown inFIG. 1A). In some embodiments, computing device110includes a hardware unit126and software127. Software127can run on hardware unit126such that various applications or programs can be executed on hardware unit126by way of software127. In some embodiments, the functions of software127can be implemented directly in hardware unit126, e.g., as a system-on-a-chip, firmware, field-programmable gate array (“FPGA”), etc. In some embodiments, hardware unit126includes one or more processors, such as processor131. In some embodiments, processor131is an execution unit, or “core,” on a microprocessor chip. In some embodiments, processor131may include a processing unit, such as, without limitation, an integrated circuit (“IC”), an ASIC, a microcomputer, a programmable logic controller (“PLC”), and/or any other programmable circuit. Alternatively, processor131may include multiple processing units (e.g., in a multi-core configuration). The above examples are exemplary only, and, thus, are not intended to limit in any way the definition and/or meaning of the term “processor.”

Hardware unit126also includes a system memory132that is coupled to processor131via a system bus234. Memory132can be a general volatile RAM. For example, hardware unit126can include a 32 bit microcomputer with 2 Mbit ROM and 64 Kbit RAM, and/or a few GB of RAM. Memory132can also be a ROM, a network interface (NIC), and/or other device(s).

In some embodiments, computing device110can also include at least one media output component or display interface136for use in presenting information to a user. Display interface136can be any component capable of conveying information to a user and may include, without limitation, a display device (not shown) (e.g., a liquid crystal display (“LCD”), an organic light emitting diode (“OLED”) display, or an audio output device (e.g., a speaker or headphones)). In some embodiments, computing device110can output at least one desktop, such as desktop140. Desktop140can be an interactive user environment provided by an operating system and/or applications running within computing device110, and can include at least one screen or display image, such as display image142. Desktop140can also accept input from a user in the form of device inputs, such as keyboard and mouse inputs. In some embodiments, desktop140can also accept simulated inputs, such as simulated keyboard and mouse inputs. In addition to user input and/or output, desktop140can send and receive device data, such as input and/or output for a FLASH memory device local to the user, or to a local printer.

In some embodiments, display image142can be presented to a user on computer displays of a remote terminal (not shown). For example, computing device110can be connected to one or more remote terminals (not shown) or servers (not shown) via a network (not shown), wherein the network can be the Internet, a local area network (“LAN”), a wide area network (“WAN”), a personal area network (“PAN”), or any combination thereof, and the network can transmit information between computing device110and the remote terminals or the servers, such that remote end users can access the information from computing device110.

In some embodiments, computing device110includes an input or a user interface150for receiving input from a user. User interface150may include, for example, a keyboard, a pointing device, a mouse, a stylus, a touch sensitive panel (e.g., a touch pad or a touch screen), a gyroscope, an accelerometer, a position detector, and/or an audio input device. A single component, such as a touch screen, may function as both an output device of the media output component and the input interface. In some embodiments, mobile devices, such as tablets, can be used.

Computing device110, in some embodiments, can include a database160within memory132, such that various information can be stored within database160. Alternatively, in some embodiments, database160can be included within a remote server (not shown) with file sharing capabilities, such that database160can be accessed by computing device110and/or remote end users. In some embodiments, a plurality of computer-executable instructions can be stored in memory132, such as one or more computer-readable storage media170(only one being shown inFIG. 1B). Computer storage medium170includes non-transitory media and may include volatile and nonvolatile, removable and non-removable mediums implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. The instructions may be executed by processor131to perform various functions described herein, e.g., steps of the method shown inFIG. 5.

FIG. 1Cillustrates an example of computer-executable instructions that can be stored in memory132as software (SW) modules. Memory132may include the following SW modules: (1) an availability window estimator SW module132athat is configured to determine a number of available time slots for delivery of groceries; (2); a map engine SW module132bthat is configured to assign delivery orders to vehicles and determine the sequence in which a particular vehicles orders will be delivered (delivery route); (3) an optimization SW module132cthat is configured to optimize the delivery route for each vehicle having at least one delivery order assigned to it.

Memory132may further store map data132dof the geographic area serviced by one or more store fronts as well as a vehicle availability database132ethat stores a snapshot of the current capacity of each vehicle in the plurality of vehicles and the time slots each vehicle has available.

Referring back toFIG. 1A, in some embodiments, server105may determine and present a number of available delivery time slots to a user. More specifically, server105may generate a synthetic order and compare the synthetic order to a snap shot of the plurality of vehicles (as described below with respect toFIG. 2) retrieved from vehicle availability database132e(shown inFIG. 1C). Server105may maintain the snap shot based on information received from vehicle server128regarding the plurality of time slots each vehicle in the plurality of vehicles has. For example, vehicle server128may transmit information regarding the number of time slots each vehicle has, and the length of each time slot. Server105may determine which vehicles among the plurality of vehicles has sufficient capacity to accommodate the synthetic order. Upon determining which vehicles have sufficient capacity, server105may insert the synthetic order into each time slot in each of the vehicles having sufficient capacity. For each time slot the synthetic order is inserted into, server105may determine whether the insertion is feasible. In other words, server105may determine if all of the vehicle's other delivery orders can be met (e.g. delivered on time) if the synthetic order is inserted into that time slot and remove those time slots that would result in the vehicle being unable to fulfill one or more of its previously scheduled deliveries. At this point, server105may identify the time slots having at least one of the plurality of vehicles available for delivery during that time slot as acceptable delivery time slots and communicate those time slots to the user via user terminals120-130.

FIG. 2illustrates a snapshot200of the time slot availability of a plurality of vehicles. Snapshot200may be updated at the end of an optimization process (as discussed in further detail below) and stored in vehicle availability database132e(shown inFIG. 1C). Each vehicle205,210,215, and220may have 4 available time slots (ranging from 1 PM to 9 PM). It should be noted that time slots of any appropriate length may be used. As discussed above, the number of time slots each vehicle has, as well as the length of each time slot may be determined based on information transmitted from each vehicle128a-cvia vehicle server128. As shown inFIG. 2, vehicle205has time slots205a-dwhile vehicle210has time slots210a-detc. In the example ofFIG. 2, vehicle210may not have any capacity, thus server105may refrain from assigning any further delivery orders to it. In addition, none of the vehicles205-225may have availability in the 1 PM-3 PM time slot, while only vehicle225has availability in the 5 PM-7 PM time slot, corresponding to time slot225c. Thus, in the example ofFIG. 2, server105may present three time slots (3 PM-5 PM, 5 PM-7 PM, and 7 PM-9 PM) to a customer wishing to place a delivery order.

Referring back toFIG. 1A, upon receiving a delivery order indicating a delivery address and a selected time slot, server105may determine a delivery route for one or more vehicles in the plurality of vehicles. More specifically, server105may determine which vehicle the received delivery order is to be assigned to, whether certain delivery orders need to be re-assigned to a different vehicle in order to optimize vehicle resources, and the sequence in which each vehicle's assigned delivery orders will be delivered. Server105may assign the received delivery order to, and determine a delivery route for a vehicle from the plurality based on the selected time slot of the received order, map data115d, and an overall cost that is a function of a number of delivery parameters. In some embodiments, server105may also re-assign delivery orders to, and determine delivery routes for other vehicles in the plurality of vehicles based on the selected time slot of the received order, map data115d, and an overall cost that is a function of a number of delivery parameters. Examples of such delivery parameters may include number of vehicles from the plurality needed to deliver all orders, total number of miles driven by the vehicles during delivery, total driving time of the vehicles during delivery, total amount of idle time of the vehicles during delivery, and degree of lateness in delivering an order (if any) among others. Server105may utilize a meta-heuristic algorithm, such as simulated annealing, in order to determine which vehicle the received delivery order is to be assigned to, as well as the sequence in which that vehicle's delivery orders are to be delivered. In addition, server105may utilize the meta heuristic algorithm to determine whether certain delivery orders need to be re-assigned to a different vehicle in order to optimize vehicle resources, and the sequence in which each vehicle's assigned delivery orders will be delivered (delivery route). In some embodiments, server105may assign a particular weight to each delivery parameter when assigning delivery orders and determining delivery routes for the one or more vehicles. For example, server105may assign total mileage the largest weight, and thus may assign delivery orders to and determine delivery routes for the one or more vehicles from the plurality of vehicles based primarily on reducing the total miles driven by the one or more vehicles, as this will have the largest impact on the overall cost. In this way, server105may determine one or more delivery routes.

FIG. 3Aillustrates a delivery route map300for a first and second delivery vehicle in accordance with some embodiments of the present disclosure. Delivery route305may indicate the delivery route of the first vehicle, while delivery route310may indicate the delivery route of the second vehicle. Delivery order315may indicate the delivery address of a delivery order that is yet to be assigned to a particular vehicle. As an initial matter, server105may determine that assigning delivery order315to the first delivery vehicle for delivery in the same time slot as delivery number2will not prevent the first delivery vehicle from completing any of its subsequent deliveries on time. Server105may make a similar determination with respect to assigning delivery order315to the second delivery vehicle for delivery in the time slot for its delivery number2. In addition, server105may determine that the delivery address of delivery order315is in close proximity to the delivery address of delivery number two for the first delivery vehicle and is also relatively far from any of the delivery addresses in the second vehicles delivery route310. Thus, server105may determine that the total number of miles required to be driven will be minimized if delivery order315is assigned to the first delivery vehicle for delivery after delivery number2. Server105may also determine that the number of miles driven can be further reduced if the first delivery vehicle delivers delivery order315after its current delivery number two (as delivery number two is on the way). Therefore, server105may assign delivery order315to the first delivery vehicle, and sequence it for delivery right after delivery number2.FIG. 3Billustrates the new delivery route for the first delivery vehicle.

In some embodiments, server105may further optimize each vehicle's delivery route. Server105may utilize any suitable local search algorithm, such as 1-0 exchange in order to calculate an optimized delivery route for each vehicle. Server105may randomly select a delivery order from among the plurality of delivery routes, and iteratively insert the randomly selected delivery order into one or more randomly selected time slots from the plurality of delivery routes. Server105may then determine the cost effect of each insertion. In some embodiments, server105may insert the randomly selected delivery order into every time slot from the plurality of delivery routes and calculate the cost effect of every insertion. In still other embodiments, server105may determine which routes among the plurality of delivery routes have available time slots that overlap with the time slot of the randomly selected delivery order. Server105may only insert the randomly selected delivery order into those routes having an available time slot that overlaps with the time slot of the randomly selected delivery order. Server105may insert the randomly selected delivery order into the time slot resulting in the largest reduction in overall cost. In some embodiments, server105may perform multiple iterations of the above described process to further optimize each vehicle's delivery route.

FIG. 4Aillustrates delivery routes for three vehicles. Server105may randomly select delivery order405corresponding to delivery number3in vehicle one's delivery route. Server105may then randomly select the time slot of delivery order410corresponding to delivery number3in vehicle two's delivery route and insert delivery order405into the time slot containing delivery order410.FIG. 4Billustrates the updated delivery routes after the insertion by server105. Server105may calculate the cost effect of inserting delivery order405into delivery order410's slot as illustrated inFIG. 4B. More specifically, server105may determine the cost effect based on an increase or decrease (if any) in the total number of miles driven by each vehicle during delivery, total driving time for each vehicle during delivery, total amount of idle time for each vehicle during delivery, number of trucks needed to deliver all orders, and degree of lateness (if any) based on inserting delivery order405into delivery order410's time slot. As discussed above, in some embodiments, certain factors (e.g. total mileage, degree of lateness) may have been assigned a greater weight, and therefore even relatively small increases in those factors may result in a significantly larger overall cost. Server105may iteratively insert delivery order405into one or more random time slots and calculate the cost effect of each such insertion. Server105may reassign delivery order405to the time slot resulting in the largest reduction in overall cost. If no time slot would result in a reduction of overall cost, server105may refrain from reassigning delivery order405.

Referring back toFIG. 1, in some embodiments, server105may assign degree of lateness a relatively heavy weight, as a late delivery can result in severe consequences (e.g. easily perishable goods going bad). However, a certain degree of lateness may be tolerable if a significant improvement in one or more other parameters is achieved by an insertion. For example, if an improvement in the overall cost due to a relatively large reduction in total mileage driven by all vehicles is achieved, and the degree of lateness will not result in goods of a delivery order perishing, then server105may allow the insertion (if the cost effect is superior to the cost effect of other insertions).

In some embodiments, server105may generate an updated snapshot of time slot availability for the plurality of vehicles and store the updated snapshot in vehicle availability database132efor presentation to online users. The updated snap shot may be based on the optimized delivery routes determined for the one or more vehicles in the plurality of vehicles.

As described above, server105may assign delivery orders and optimize delivery routes whenever a new delivery order is received from a user terminal120-135. In some embodiments, server105may continuously optimize the delivery routes of each vehicle at pre-defined intervals until a pre-defined time period before the delivery route is to commence. In other embodiments, server105may optimize delivery routes in response to receiving a new delivery order until a pre-defined time period before the delivery route is to commence.

In some embodiments, server105may transmit the optimized delivery routes to the corresponding vehicles among the plurality of vehicles128a-cvia vehicle server128, which may act as a relay to provide the optimized delivery routes to the corresponding vehicles.

FIG. 5illustrates a flow diagram of a method500for optimizing delivery vehicle resources in accordance with some exemplary embodiments of the present disclosure. Method500may be performed by, server105described with respect toFIG. 1, for example.

At505, server105may determine a number of available delivery time slots and present them to a user. More specifically, server105may generate a synthetic order and compare the synthetic order to a snap shot of the time slot availability of the plurality of vehicles (as described above with respect toFIG. 2) retrieved from vehicle availability database132e(shown inFIG. 1C). Server105may maintain the snap shot based on information received from vehicle server128regarding the plurality of time slots each vehicle in the plurality of vehicles has. For example, vehicle server128may transmit information regarding the number of time slots each vehicle has, and the length of each time slot. Server105may determine which vehicles among the plurality of vehicles has sufficient capacity to accommodate the synthetic order. Upon determining which vehicles have sufficient capacity, server105may insert the synthetic order into each time slot in each of the vehicles having sufficient capacity. For each time slot the synthetic order is inserted into, server105may determine whether the insertion is feasible. In other words, server105may determine if all of the vehicle's other delivery orders can be met (e.g. delivered on time) if the synthetic order is inserted into that time slot and remove those time slots that would result in the vehicle being unable to fulfill one or more of its previously scheduled deliveries. At this point, server105may identify the time slots having at least one of the plurality of vehicles available for delivery during that time slot as acceptable delivery time slots and present them to the user via user terminals120-130.

At510server105may determine whether a delivery order has been received. If server105determines that a delivery order has been received, at515, server105may determine which vehicle the received delivery order is to be assigned to, and whether certain delivery orders need to be re-assigned to a different vehicle in order to optimize vehicle resources. At520, server105may determine the sequence in which the assigned vehicle's delivery orders will be delivered. Server105may assign delivery orders to, and determine a delivery route for the vehicle based on the selected time slot of the received order, map data132d, and an overall cost that is a function of a number of delivery parameters. In some embodiments, server105may also re-assign delivery orders to and determine delivery routes for other vehicles in the plurality of vehicles based on the selected time slot of the received order, map data132d, and an overall cost that is a function of a number of delivery parameters. Examples of such delivery parameters may include number of vehicles from the plurality needed to deliver all orders, total number of miles driven by the vehicles during delivery, total driving time of the vehicles during delivery, total amount of idle time of the vehicles during delivery, and degree of lateness in delivering an order (if any) among others. Server105may utilize a meta-heuristic algorithm, such as simulated annealing, in order to determine which vehicle the received delivery order is to be assigned to, as well as the sequence in which that vehicle's delivery orders are to be delivered. In addition, server105may utilize the meta heuristic algorithm to determine whether certain delivery orders need to be re-assigned to a different vehicle in order to optimize vehicle resources, and the sequence in which each vehicle's assigned delivery orders will be delivered (delivery route). In some embodiments, server105may assign a particular weight to each delivery parameter when assigning delivery orders and determining delivery routes for the one or more vehicles. For example, server105may assign total mileage the largest weight, and thus may assign delivery orders to and determine delivery routes for the one or more vehicles from the plurality of vehicles based primarily on reducing the total miles driven by the one or more vehicles, as this will have the largest impact on the overall cost. In this way, server105may determine one or more delivery routes.

At525, server105may further optimize each vehicle's delivery route. Server105may utilize any suitable local search algorithm, such as 1-0 exchange in order to calculate an optimized delivery route for each vehicle. Server105may utilize any suitable local search algorithm, such as 1-0 exchange in order to calculate an optimized delivery route for each vehicle. Server105may randomly select a delivery order from among the plurality of delivery routes, and iteratively insert the randomly selected delivery order into one or more randomly selected time slots from the plurality of delivery routes. Server105may then determine the cost effect of each insertion. In some embodiments, server105may insert the randomly selected delivery order into every time slot from the plurality of delivery routes and calculate the cost effect of every insertion. In still other embodiments, server105may determine which routes among the plurality of delivery routes have available time slots that overlap with the time slot of the randomly selected delivery order Server105may only insert the randomly selected delivery order into those routes having an available time slot that overlaps with the time slot of the randomly selected delivery order. Server105may insert the randomly selected delivery order into the time slot resulting in the largest reduction in overall cost. In some embodiments, server105may perform multiple iterations of the above described process.

In some embodiments, server105may generate an updated snapshot of time slot availability for the plurality of vehicles and store the updated snapshot in vehicle availability database132efor presentation to online users. The updated snap shot may be based on the optimized delivery routes determined for the one or more vehicles in the plurality of vehicles.

As described above, server105may assign delivery orders and optimize delivery routes whenever a new delivery order is received from a user terminal120-135. In some embodiments, server105may continuously optimize the delivery routes of each vehicle at pre-defined intervals until a pre-defined time period before the delivery route is to commence. In other embodiments, server105may optimize delivery routes in response to receiving a new delivery order until a pre-defined time period before the delivery route is to commence.

In some embodiments, server105may transmit the optimized delivery routes to the corresponding vehicles among the plurality of vehicles128a-cvia vehicle server128, which may act as a relay to provide the optimized delivery routes to the corresponding vehicles.

In some embodiments, a delivery system may include a hierarchical distribution architecture that includes one or more hubs and one or more spokes. Hubs, for example, may be a distribution center or supercenter that stores goods for order fulfillment. Spokes may be, for example, more locally centralized distribution centers that can store orders received from a hub. The spokes may hold order contents for delivery to customer locations, such as to customer homes. By incorporating one or more spokes to the delivery system, a delivery area served by a hub may be expanded. For example, vehicles, such as vans, can deliver orders from hubs to spokes, and then other vehicles can deliver the orders from the spokes to their delivery destination.

For example,FIG. 6illustrates an example delivery system600that includes a hub602, and spokes604,606,608. Hub602may be a supercenter that fulfills customer orders, and spokes604,606,608may be warehouses that can store orders, for example. As indicated inFIG. 6, hub602may serve (e.g., deliver to or pick up from) an area (e.g., catchment)610. For example, the delivery system600may include vehicles that are associated with hub602and serve locations within area610. Similarly, spoke604may serve area612, spoke606may serve area614, and spoke608may serve area616.

FIG. 6also illustrates various customer locations. For example, area610includes customer locations620,622, and624. A vehicle, for example, may deliver an order from hub602to one or more of customer locations620,622, and624. Similarly, a vehicle may pick up an order from one or more of customer locations620,622, and624for delivery to hub602. For example, as indicated by route618, a vehicle may leave hub602and stop first at customer location620. The vehicle may execute (e.g., deliver or pick up) an order first at customer location620. The vehicle may then continue to customer location622to execute a second order, and then leave customer location622and continue to customer location624to execute a third order. The vehicle may make proceed to spoke608before returning to hub602. If the vehicle is delivering orders to any of customer locations620,622, and624, the vehicle would be loaded with the order contents before leaving hub602. If the vehicle is picking up an order from any of customer locations620,622, and624, the contents of the order may be picked up at the respective customer location620,622,624and unloaded at hub602when the vehicle returns to hub602.

In addition, vehicles associated with hub602may serve spokes604,606,608. For example, a vehicle may deliver orders to, or pick up orders from, spokes604,606,608. As indicated in the illustration, a vehicle may follow route650which may start at hub602, and continue on to each of spokes604and606before returning to hub602. As indicated earlier, route618may include a stop at spoke608. As such, order contents may be delivered between hub602and one or more of spokes604,606,608.

Area612, which is served by spoke604, may include one or more customer locations628,630, and632. As indicated by route626, a vehicle may execute orders at one or more of customer locations628,630, and632. For example, beginning at spoke604, a vehicle following route626may execute an order at customer location628, continue to customer location630to execute another order, and then proceed to customer location632to execute a third order. The vehicle may then return to spoke604. If the vehicle is delivering goods to any of customer locations628,630,632, the vehicle may be loaded with the goods at spoke604before proceeding on route626. Otherwise, if the vehicle is picking up an order from any of customer locations628,630,632, the vehicle may pick up the order from the customer location and deliver it to spoke604upon the vehicle's return.

For example, a customer may place an order for a delivery to customer location630. The order may be fulfilled at hub602. The order contents may be loaded onto a vehicle, and delivered to spoke604via route650. Upon arriving at spoke604, the contents may be unloaded and stored within spoke604. The order contents may then be loaded onto a different vehicle that delivers along route626. The vehicle would leave spoke604following route626and, upon arriving at customer location630, deliver the contents.

Similarly, a vehicle may pick up an order from a customer location for delivery back to hub602, for example, such as a return. For example, a first vehicle would pick up the contents of the order at the customer location, such as customer location630, and proceed along route626until arriving at spoke604. Once the vehicle arrives at spoke604, the contents may be unloaded and stored at spoke604. To deliver the contents to hub602, the contents may be loaded on a vehicle assigned to route650. Upon reaching hub602, the contents of the order may be unloaded and stored at hub602.

Area614, which is served by spoke606, may include one or more customer locations632,636,638, and640. A vehicle following route634may execute orders at one or more of customer locations636,638, and640. For example, begging at spoke606, a vehicle following route634may execute an order at customer location636, continue to customer location638to execute a second order, and then proceed to customer location640to execute a third order. The vehicle may then return to spoke606. If the vehicle is delivering goods to any of customer locations636,638, and640, the vehicle may be loaded with the goods at spoke606before proceeding on route634. Otherwise, if the vehicle is picking up an order from any of customer locations636,638,640, the vehicle may pick up the order from the customer location and deliver it to spoke606upon the vehicle's return.

Although customer location632is in area614, it is also in area612. In some examples, a customer location is served by a particular spoke. In this example, customer location632is served by spoke604as discussed above. In some examples, the areas are based on postal code. For example, if spoke604is assigned to serve customer locations within postal code 90001, spoke606is assigned to serve customer locations within postal code 90002, and customer location632is located within postal code 90001, only spoke604will serve customer location632. In some examples, the serving spoke is based on distance to a customer location. For example, if a service area of spoke604overlaps with a service area of spoke606at customer location632, the spoke closest to the customer location632will serve customer location632. For example, if customer location632is two miles away from spoke604, and three miles away from spoke606, then only spoke604will serve customer location632. However, in other examples, a customer location may be served my multiple spokes. For example, customer location632may be served by both spokes604and606.

Because spoke606is also in area610served by hub602, goods may be transported between hub602and one or more customer locations636,638, and640. For example, the goods may be transported between hub602and spoke606via route650, and between spoke606and any of customer locations636,638,640via route634.

Area616, which is served by spoke608, may include one or more customer locations644,646, and648. As indicated by route642, a vehicle may execute orders at one or more of customer locations644,646, and648. For example, begging at spoke608, a vehicle following route642may execute an order at customer location644, continue to customer location646to execute another order, and then proceed to customer location648to execute a third order. The vehicle may then return to spoke608. If the vehicle is delivering goods to any of customer locations644,646, and648, the vehicle may be loaded with the goods at spoke608before proceeding on route642. Otherwise, if the vehicle is picking up an order from any of customer locations644,646,648, the vehicle may pick up the order from the customer location and deliver it to spoke608upon the vehicle's return.

Because spoke608is also in area610, goods may be transported between hub602and one or more customer locations644,646, and648. For example, the goods may be transported between hub602and spoke608via route650, and between spoke608and any of customer locations644,646,648via route642.

In some examples, multiple catchments can be setup at hubs and spokes with no overlaps in the catchments. In addition, each catchment can have its own order delivery mechanism (e.g., its own vehicle fleet, 3rd party carrier, etc.).

FIG. 7illustrates a diagram700of vehicle availability that may be used, for example, with the system600shown inFIG. 6. Along the bottom, the diagram includes a timeline701that identifies the times of a day. The diagram also includes pick-up/delivery time slots710that identify windows of time along timeline701that a customer, executing an order in an area served by spoke704, may execute an order (e.g., have an order delivered or picked up). For example, time slots710may include windows of time that a customer may have an order delivered to their home. In addition, the diagram includes pick-up/delivery hub shifts708that identify windows of time along timeline701that a vehicle, servicing spoke704, is available for order execution, for example, along a route from spoke704that serves the customer.

The diagram ofFIG. 7also includes pick-up/delivery time slots706that identify windows of time along timeline701that a customer, executing an order in an area served by hub702, may execute an order. For example, time slots706may include windows of time that a customer may have an order delivered to their home.

In addition, the diagram includes pick-up/delivery hub shifts708that identify windows of time along timeline701that a vehicle, servicing hub702and spoke704, is available for order execution. For example, hub shifts708may include windows of time that a vehicle is available to proceed along a route from hub702to spoke704. Each hub shift708may include a hub start time, and a hub end time. The hub end time may be offset by the hub start time by a time window width (i.e., hub start time+time window width=hub end time).

Similarly, the diagram includes pick-up/delivery spoke shifts712that identify windows of time along timeline701that a vehicle, servicing spoke704and a customer, is available for order execution. For example, spoke shifts712may include windows of time that a vehicle is available to proceed along a route from spoke704to a customer. Each spoke shift712may include a spoke start time, and a spoke end time. The spoke end time may be offset by the spoke start time by a time window width (i.e., spoke start time+time window width=spoke end time).

Time slots706and710may be, for example, similar to the time slots discussed above with respect toFIG. 2. For example, server105may also maintain a database of vehicle availability, such as hub and spoke time shifts708and710, which it may use to determine available time slots for presentation to a user (e.g., via user terminals120,125, and130ofFIG. 1). Based upon what time slot710a customer selects, the one or more hub and spoke shifts708,710may be determined for order execution. For example, based a time slot710selected by a customer for delivery of an order in an area serviced by spoke704, a hub shift708may be selected, during a vehicle is to deliver the order contents from hub702to spoke704. In addition, a spoke shift712may be determined to have the order contents delivered from spoke704to the destination location. For example, based on the selected hub shift708, a spoke shift712may be selected to have a vehicle deliver the order contents from the spoke704to the order destination.

In some examples a server, such as server105, which may be located at hub702, may select a hub shift708and a spoke shift710for an order. In some examples, a local server, such as one located at a spoke, such as spoke704, may determine the hub shift708and the spoke shift712for an order.

In one example, the hub and spoke shifts708,710are determined in the following manner. Given a requested order execution time slot710for an order execution in an area served by spoke704, the earliest starting spoke shift712that overlaps in time with the requested order execution time slot710is selected. For example, assume time slot23was requested. Both spoke shifts22and23overlap in time with time slot23. However, spoke shift22has an earlier starting time than spoke shift23. Thus, spoke shift22is selected. The selected spoke shift22represents the vehicle shift (e.g., time window) that the order contents will be delivered to, or picked up from, the order's delivery/pick-up location. In some examples, the selected starting spoke shift712must overlap in time with the requested execution time slot710by at least a threshold amount (e.g., 30 minutes).

Based on the selected spoke shift712, a hub shift708is selected. The selected hub shift708may have an ending time that is a minimum amount of time before the start of the selected spoke shift712. For example, the selected spoke shift712may have an ending time that is before the start of the selected spoke shift712by a transport time, which may be the estimated amount of time that it takes to transport goods from hub702to spoke704. In some examples, the minimum amount of time includes a lead time. The lead time may be a buffer amount of time that attempts to ensure that the vehicle has enough time to deliver the goods to the spoke704before the selected spoke shift712begins. In some examples, the minimum amount of time includes one or more of the following: an amount of time it takes to load goods onto a vehicle at the hub (e.g., hub loading time), an amount of time it takes to unload the goods at the spoke (e.g., spoke unloading time), and an amount of time it takes to load the goods onto a vehicle at the spoke for customer delivery (e.g., spoke loading time). The minimum amount of time may include one or more of the transport time, the lead time, the hub loading time, the spoke unloading time, and the spoke loading time.

For example, as shown inFIG. 7, the amount of time between hub shift10and spoke shift21is identified as “X.” If X is equal to or greater than the minimum amount of time, then hub shift10may be used to deliver goods from hub702to spoke704such that the goods may be placed on a vehicle servicing an area serviced by spoke704during spoke shift21. In one example, the minimum amount of time is equal to the transit time between hub702and spoke704, and a lead time. In one example, the minimum amount of time is equal to the transit time between hub702and spoke704, the loading time at hub702, the unloading time at spoke704, the loading time at spoke704, and a lead time.

In some examples, orders for a same time slot710,706that are to be delivered to a same location, such as spoke704, may be combined and delivered concurrently. For orders that are to be delivered from a hub directly to a customer (e.g., a customer location within the area served by the hub), a customer may select a hub time slot706.

In some examples, a hub start time for a hub shift708must be less than or equal to a spoke start time for a spoke shift712. In some examples, new customer orders are not accepted (e.g., “cut-off”) at a spoke before they are not allowed at a corresponding hub. For example, a spoke cut-off time for a spoke shift712would be required to be less than or equal to a hub cut-off time for a hub shift708. In this manner, cut-off times for all spokes served by a hub would happen at the same time as, or before, the cut-off time for the serving hub.

FIG. 8Aillustrates a flow diagram representing an example application programming interface (API)802that may be used to view time slots available for vehicle deliveries using, for example, the system100shown inFIG. 1A. The time slots shown may correspond, for example, to the hub time slots706or spoke time slots710ofFIG. 7. At step804, a view slot request is received. For example, a terminal, such as terminals120,125, and130ofFIG. 1, may transmit a view slot request to server105ofFIG. 1. The view slot request may be a request to view available time slots for order execution, such as order delivery or pick-up, over a period of time (e.g., a week). At step806, for each day requested, a time slot solution is requested. The time slot solution may be one or more time slots that may be available for order execution on a particular day.

At step808, insertion heuristics are executed for each available slot for a particular day. Insertions heuristics relate to logic that system100may use to determine whether a new customer order can be accepted, within an acceptable cost. The factors to be considered may include, for example, vehicle capacity, total travel time and distance, whether other orders will be affected, etc. For example, server105may determine whether the customer may place an order for each time slot returned in step806by determining whether one or more of a hub shift and a spoke shift are available to deliver to the customer the contents associated with the order, such as described with respect toFIG. 6. At step810, time slots that have been determined to be available are returned. For example, server105may send one or more time slots that have been determined to be available for order execution to one or more of terminals120,125, and130for display.

FIG. 8Billustrates a flow diagram representing an example API812that may be used to book time slots available for vehicle deliveries using, for example the system100shown inFIG. 1A. The time slots shown may correspond, for example, to the hub time slots706or spoke time slots710ofFIG. 7. At step814, a book slot request is received. A book slot request may be received, for example, when a customer places an item for purchase in their online shopping cart. The book slot request may be received by, for example, server105from a terminal, such as terminals120,125, and130. At step816, for each day requested, a time slot solution is requested. The time slot solution may be one or more time slots that may be available for order execution on a particular day. At step818, insertion heuristics are executed for the time slot to determine whether the time slot can be booked. For example, server105may determine whether the customer may book the time slot returned in step816by determining whether one or more of a hub shift and a spoke shift are available to deliver to the customer the contents associated with the order, such as described with respect toFIG. 6. At step820, if the time slot was successfully book, the method ends. Otherwise, if the time slot was not able to be book, the method proceeds back to step816, where the booking of another time slot may be attempted. The booked time slot may be sent by server105to one or more of terminals120,125,130for display.

FIG. 8Cillustrates a flow diagram representing an example API822that may be used to update time slots available for vehicle deliveries using, for example, the system100shown inFIG. 1A. The time slots shown may correspond, for example, to the hub time slots706or spoke time slots710ofFIG. 7. At step824, an update slot request is received. In some examples, the update slot request is received when a customer completes checkout, such that the order weight and volume capacity has been determined. The update slot request may be received by, for example, server105from a terminal, such as terminals120,125, and130. At step826, for each time slot for each day requested, a time slot solution is requested. The time slot solution may be one or more time slots that may be available for order execution on the particular day. At step828, the update is made, including any necessary route adjustments. For example, if the day of the order changed, then the existing route is changed to remove the order from it, and instead the order is added to a route that available during the updated time slot. At step830, if the time slot was successfully updated, the method ends. Otherwise, if the time slot was not successfully updated, the method proceeds back to step826, where the update is attempted for a different time slot. The updated time slot may be sent by server105to one or more of terminals120,125,130for display.

FIG. 9illustrates a flow diagram of a method900for optimizing a plurality of vehicle delivery routes in a hierarchical distribution design, such as the example delivery system600described with respect toFIG. 6. At step902, a selected slot for a delivery order is received from a user terminal. The delivery order is to be delivered at a delivery location in a first geographical area. The first geographical area may be, for example, an area serviced by a spoke, such as one of spokes604,606,608ofFIG. 6. At step904, a delivery time period from deliver from a location in the first geographical area to the delivery location is determined. The determination includes determining that the delivery time period at least partially coincides in time with the selected time slot.

At step906, a pick-up time period for order pick-up from a location in a second geographical area for delivery to the location in the first geographical area is determined. The determination is based on a start time of the delivery time period determined is step904. The second geographical area may be, for example, an area served by a hub, such as hub602ofFIG. 6. At step908, order instructions are transmitted to a first vehicle server. The instructions include instructions to pick up the order contents from the location in the second geographical area, and to drop off the order contents at the location in the first geographical area. For example, the instructions may include instructions to proceed on a route from a hub to a spoke for delivery of the order contents. At step910, order instructions are transmitted to a second vehicle server. The instructions include instructions to pick up the order from the location in the first geographical area, and to drop off the order at the delivery location during the selected time slot. For example, the instructions may include instructions to proceed on a route from a spoke to a customer's home for delivery of the order contents.

FIG. 10illustrates a flow diagram of a method1000for optimizing a plurality of vehicle delivery routes in a hierarchical distribution design, such as the example delivery system600described with respect toFIG. 6. At step1002, a server, such as server105ofFIG. 1, receives, from a first vehicle server, first shift data for a first plurality of vehicles. The first shift data includes a plurality of first time periods, where each first time period corresponds to a window of time that a vehicle of the first plurality of vehicles is available for execution of orders in a first geographical area. For example, first shift data can include one or more hub shifts as described with respect toFIG. 6.

At step1004, the server receives, from a second vehicle server, second shift data for a second plurality of vehicles. The second shift data includes a plurality of second time periods, where each second time period corresponds to a window of time that a vehicle of the second plurality of vehicles is available for execution of orders in the second geographical area. For example, first shift data can include one or more spoke shifts as described with respect toFIG. 6.

At step1006, the server receives, from a user terminal, a selected time slot for a requested order at a requested order location in the second geographical area. At step1008, the server determines a second time period of the plurality of second time periods that overlaps in time with the selected time slot by a threshold amount. At step1010, the server determines a first time period of the plurality of first time periods based on a minimum amount of time between end times of the plurality of first time periods and the start time of the determined second time period. The minimum amount of time can include, for example, a transit time and a lead time. In this example, the determined first time period has the smallest time difference that is still greater than the minimum amount of time.

At step1012, the server transmits, to the first vehicle server, a first order assignment for the requested order from a pick-up location in the first geographical area to a drop-off location in the second geographical area during the determined first time period. For example, the first order assignment can include instructions to deliver goods from a hub in the first geographical area to a spoke in the second geographical area. At step1014, the server transmits, to the second vehicle server, a second order assignment for the requested order from the drop-off location in the second geographical area to the requested order location in the second geographical area during the determined second time period. For example, the second order assignment can include instructions to deliver the goods from the spoke in the second geographical area to the requested order location.