Constrained service restoration with heuristics

• US 9,188,453 B2
• Filed: 09/30/2013
• Issued: 11/17/2015
• Est. Priority Date: 03/07/2013
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Ball, Kathy, Hopping, Albert
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): Troost, Aaron L
• Application Number:
  US14/041,423
• Publication Number:
  US 20140257694A1
• Time in Patent Office: 778 Days
• Field of Search: 701/527, 455/521
• US Class Current: 1/1
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 50/06 Energy or water supply

Abstract

A method of determining service routes for a plurality of crews is provided. Outage data identifying a plurality of service outage source locations, a number of affected customers associated with each location of the plurality of locations, and a type of repair to perform at each location of the plurality of locations is received. A repair time is estimated for each location. Crew data identifying a plurality of crews and a start location for the plurality of crews is received. A service route for each crew is determined based on a crew skill indicator associated with each crew satisfying the type of repair to perform at each location and based on the estimated repair time for each location. The service route for a crew of the plurality of crews includes the start location as a first location and at least one location of the plurality of locations.

Claims

1. A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:

receive outage data identifying a plurality of service outage source locations, a number of affected customers associated with each location of the plurality of locations, and a type of repair to perform at each location of the plurality of locations;

receive crew data identifying a plurality of crews;

estimate a repair time for each location of the plurality of locations;

estimate a travel time between pairs of locations of the plurality of locations;

calculate a number of customers restored per a predefined time period for the pairs of locations of the plurality of locations based on the estimated travel time and the estimated repair time;

determine a service route for each crew of the plurality of crews based on a crew skill indicator associated with each crew satisfying the type of repair to perform at each location of the plurality of locations and based on the calculated number of customers restored, wherein the service route for each crew of the plurality of crews includes a plurality of repair locations of the plurality of locations;

store at least a first repair location of the determined service route for sending electronically to a respective crew of the plurality of crews; and

electronically send at least the first repair location of the determined service route to a second computing device different from the computing device, wherein at least the first repair location is presented on a display communicably connected to the second computing device to notify the respective crew of their first repair location.

2. The computer-readable medium of claim 1, wherein the estimated repair time for each location of the plurality of locations is determined based on a probability function.

3. The computer-readable medium of claim 2, wherein the probability function is defined based on the type of repair to perform at each location of the plurality of locations.

4. The computer-readable medium of claim 3, wherein the probability function is further defined based on analysis of a dataset of actual repair times based on the type of repair.

5. The computer-readable medium of claim 1, wherein the estimated repair time for each location of the plurality of locations is a constant value defined as a function of the type of repair to perform at each location of the plurality of locations.

6. The computer-readable medium of claim 1, wherein the computer-readable instructions further cause the computing device to estimate a travel time between each location of the plurality of locations, wherein the service route determined for each crew of the plurality of crews is further based on the estimated travel time between each location of the plurality of locations.

7. The computer-readable medium of claim 6, wherein the estimated travel time for each location of the plurality of locations is based on a distance between a pair of locations of the plurality of locations and a speed.

8. The computer-readable medium of claim 7, wherein the distance is determined based on existence of a road between the pair of locations.

9. The computer-readable medium of claim 8, wherein the speed is determined based on a condition of the road between the pair of locations.

10. The computer-readable medium of claim 6, wherein the estimated travel time between the pair of locations of the plurality of locations is determined based on a probability function.

11. The computer-readable medium of claim 1, wherein a start location is the same for each crew of the plurality of crews and the start location is a starting point for the determined service route.

12. The computer-readable medium of claim 1, wherein the crew data further identifies a maximum work time for each crew of the plurality of crews, wherein the service route determined for each crew of the plurality of crews is further based on a work time for each crew being less than or equal to the maximum work time for the respective crew.

13. The computer-readable medium of claim 1, wherein the computer-readable instructions further cause the computing device to:

receive updated outage data identifying a remaining plurality of service outage source locations and a number of affected customers associated with each location of the remaining plurality of locations;

receive updated crew data identifying a current crew location for the plurality of crews;

estimate an updated travel time between pairs of locations of the remaining plurality of locations;

calculate an updated number of customers restored per an updated predefined time period for the pairs of locations of the remaining plurality of locations based on the estimated updated travel time and the estimated repair time; and

determine an updated service route from the current crew location for each crew of the plurality of crews based on the calculated updated number of customers restored for each remaining location of the remaining plurality of locations.

14. The computer-readable medium of claim 13, wherein the computer-readable instructions further cause the computing device to store at least a next repair location of the determined updated service route for sending to the respective crew of the plurality of crews.

15. The computer-readable medium of claim 1, wherein a service outage at the plurality of service outage source locations is a power outage and the type of repair is selected from the group consisting of tree cutting, overhead line repair, underground line repair, overhead transformer repair, underground transformer repair, overhead transformer replacement, and underground transformer replacement.

16. The computer-readable medium of claim 1, wherein the service route for the crew of the plurality of crews includes a start location as a last location of the crew.

17. The computer-readable medium of claim 1, wherein the computer-readable instructions further cause the computing device to minimize a total customer time without a service subject to the crew skill indicator satisfying the type of repair to perform at each location of the plurality of locations using a mixed integer linear program with the determined service route for each crew of the plurality of crews as an initial condition.

18. The computer-readable medium of claim 1, wherein determining the service route for each crew of the plurality of crews comprises:

(a) selecting a crew of the plurality of crews;

(b) removing each pair of locations of the pairs of locations that include an endpoint location at which the crew skill indicator for the selected crew does not satisfy the type of repair to perform at the endpoint location or that is already assigned to a crew, thereby defining acceptable next locations for the selected crew;

(c) selecting a next location from the acceptable next locations based on the calculated number of customers restored per the predefined time period;

(d) updating a location of the selected crew as the selected next location; and

(e) repeating (b)-(d) with a next crew as the selected crew until the updated location is selected for each crew of the plurality of crews.

19. The computer-readable medium of claim 18, wherein selecting the next location from the acceptable next locations is based on maximizing the number of customers restored.

20. The computer-readable medium of claim 1, wherein the predefined time period is selected from the group consisting of a minute, five minutes, ten minutes, twenty minutes, thirty minutes, forty minutes, fifty minutes, and an hour.

21. The computer-readable medium of claim 1, wherein the pairs of locations are selected based on current locations of the plurality of crews.

22. The computer-readable medium of claim 1, wherein determining the service route for each crew of the plurality of crews comprises:

(a) initializing a shift work time as a shift start time for the plurality of crews;

(b) selecting a crew of the plurality of crews;

(c) removing each pair of locations of the pairs of locations that include an endpoint location at which the crew skill indicator for the selected crew does not satisfy the type of repair to perform at the endpoint location or for which a crew has been assigned or for which a maximum work time for the crew is exceeded, thereby defining acceptable next locations for the selected crew;

(d) based on only one next location of the acceptable next locations being a last location defined for the crew, selecting a next location as the last location and indicate a crew shift as complete;

(e) based on more than one next location of the acceptable next locations being the last location defined for the crew, selecting a next location from the acceptable next locations based on the calculated number of customers restored per the predefined time period;

(f) updating a location of the selected crew as the selected next location;

(g) updating a shift work time based on the estimated repair time for the selected next location and based on the estimated travel time to the selected next location;

(h) repeating (c)-(g) with a next crew as the selected crew until the updated location is selected for each crew of the plurality of crews for which the crew shift is incomplete; and

(i) repeating calculation of the number of customers restored and (b)-(h) until the crew shift of each crew of the plurality of crews is complete.

23. The computer-readable medium of claim 1, wherein determining the service route for each crew of the plurality of crews comprises:

(a) initializing a shift work time as a shift start time for the plurality of crews;

(b) selecting a crew of the plurality of crews;

(c) removing each pair of locations of the pairs of locations that include an endpoint location at which the crew skill indicator for the selected crew does not satisfy the type of repair to perform at the endpoint location or for which a crew has been assigned or for which a maximum work time for the crew is exceeded, thereby defining acceptable next locations for the selected crew;

(d) based on only one next location of the acceptable next locations being a last location defined for the crew, selecting a next location as the last location and indicate a crew shift as complete;

(e) based on more than one next location of the acceptable next locations being the last location defined for the crew, selecting a next location from the acceptable next locations based on the calculated number of customers restored per the predefined time period;

(f) updating a location of the selected crew as the selected next location;

(g) updating a shift work time based on the estimated repair time for the selected next location and based on the estimated travel time to the selected next location;

(h) repeating (c)-(g) with a next crew as the selected crew until the updated location is selected for each crew of the plurality of crews for which the crew shift is incomplete;

(i) repeating calculation of the number of customers restored and (b)-(h) until the crew shift of each crew of the plurality of crews is complete; and

(j) repeating (a)-(i) with the shift start time defined as a next shift start time.

24. The computer-readable medium of claim 23, wherein (j) is repeated for a second plurality of crews different from the plurality of crews.

25. The computer-readable medium of claim 1, wherein determining the service route for each crew of the plurality of crews comprises:

(a) selecting a crew of the plurality of crews;

(b) based on the crew skill indicator being assigned to the selected crew, removing each pair of locations of the pairs of locations that include an endpoint location at which the crew skill indicator for the selected crew does not satisfy the type of repair to perform at the endpoint location or that is already assigned to a crew, thereby defining acceptable next locations for the selected crew;

(c) based on no crew skill indicator being assigned to the selected crew, removing each pair of locations of the pairs of locations that is already assigned to a crew, thereby defining acceptable next locations for the selected crew;

(d) selecting a next location from the acceptable next locations based on the calculated number of customers restored per the predefined time period;

(e) based on no crew skill indicator being assigned to the selected crew, assigning a crew skill indicator to the selected crew based on the type of repair to perform at the selected next location;

(f) updating a location of the selected crew as the selected next location; and

(g) repeating (b)-(f) with a next crew as the selected crew until the updated location is selected for each crew of the plurality of crews.

26. A system comprising:

a processor; and

a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the system to

receive outage data identifying a plurality of service outage source locations, a number of affected customers associated with each location of the plurality of locations, and a type of repair to perform at each location of the plurality of locations;

receive crew data identifying a plurality of crews;

estimate a repair time for each location of the plurality of locations;

estimate a travel time between pairs of locations of the plurality of locations;

calculate a number of customers restored per a predefined time period for the pairs of locations of the plurality of locations based on the estimated travel time and the estimated repair time;

determine a service route for each crew of the plurality of crews based on the crew skill indicator satisfying the type of repair to perform at each location of the plurality of locations and based on the calculated number of customers restored, wherein the service route for each crew of the plurality of crews includes a plurality of repair locations of the plurality of locations;

store at least a first repair location of the determined service route for sending electronically to a respective crew of the plurality of crews; and

electronically send at least the first repair location of the determined service route to a second computing device, wherein at least the first repair location is presented on a display communicably connected to the second computing device to notify the respective crew of their first repair location.

27. A method of determining service routes for a plurality of crews, the method comprising:

receiving, at a first device, outage data identifying a plurality of service outage source locations, a number of affected customers associated with each location of the plurality of locations, and a type of repair to perform at each location of the plurality of locations;

receiving, at the first device, crew data identifying a plurality of crews;

estimating, by the first device, a repair time for each location of the plurality of locations;

estimating, by the first device, a travel time between pairs of locations of the plurality of locations;

calculating, by the first device, a number of customers restored per a predefined time period for the pairs of locations of the plurality of locations based on the estimated travel time and the estimated repair time;

determining, by the first device, a service route for each crew of the plurality of crews based on the crew skill indicator satisfying the type of repair to perform at each location of the plurality of locations and based on the calculated number of customers restored, wherein the service route for each crew of the plurality of crews includes a plurality of repair locations of the plurality of locations;

storing at least a first repair location of the determined service route for sending electronically to a respective crew of the plurality of crews; and

electronically sending at least the first repair location of the determined service route from the first device to a second device, wherein at least the first repair location is presented on a display communicably connected to the second device to notify the respective crew of their first repair location.