Constrained service restoration with heuristics
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-021/34
G06Q-010/04
G06Q-010/06
G06Q-050/06
출원번호
US-0041423
(2013-09-30)
등록번호
US-9188453
(2015-11-17)
발명자
/ 주소
Ball, Kathy
Hopping, Albert
출원인 / 주소
SAS Institute Inc.
대리인 / 주소
Bell & Manning, LLC
인용정보
피인용 횟수 :
0인용 특허 :
19
초록▼
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 plu
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.
대표청구항▼
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 eac
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; andelectronically 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; anddetermine 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; anda 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; andelectronically 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; andelectronically 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.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (19)
Chauhan, Swatantar K.; Guman, Michael A.; Palmer, Christopher M.; Wilson, Frank; O'Neill, Adrian I.; Dinkins, Jason; Sanders, David, Automated utility supply management system integrating data sources including geographic information systems (GIS) data.
Dahlgren,Darwin; Dahlgren,Nicoline; Dahlgren,Dean; Chao,Tah Wei; Fritsch,Michael R.; Kadlec,Anthony; Pellegrino,Michael John, Centralized facility and intelligent on-board vehicle platform for collecting, analyzing and distributing information relating to transportation infrastructure and conditions.
Cahill O'Brien,Barry; Osterloh,Christopher; Nagy,Christopher J., Distributed utility monitoring, such as for monitoring the quality or existence of a electrical, gas, or water utility.
Berger, Thomas R; Denny, Joseph E.; Robins, David S.; Wallace, Stephen A.; Gurgone, Raymond T.; Koop, LaMonte Peter; Payne, Edward Allen; Twitchell, Robert W.; Hilton, Rodney A.; Edwards, Randy, Managing and monitoring emergency services sector resources.
Flockhart, Andrew D.; Roybal, Larry John; Steiner, Robert C., Method and apparatus for supporting individualized selection rules for resource allocation.
Storch Joan A. ; Storch Danny L., Method and system for processing a service request relating to installation, maintenance or repair of telecommunication.
Fedorov, Boris; Silver, Jason Reid; Buettner, Kathleen June; McLelland, David; Keswani, Claude, Scheduling via multiple dimensions including worker, time, and location.
Horstemeyer, Scott A., Systems and methods for a notification system that enable user changes to stop location for delivery and/or pickup of good and/or service.
Mason, Jr.,Robert T; Borleske,Andrew J; Shuey,Kenneth C, Using a fixed network wireless data collection system to improve utility responsiveness to power outages.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.