Vending machine service scheduling

• US 7,894,938 B1
• Filed: 03/31/2005
• Issued: 02/22/2011
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: Cantaloupe, Inc.
• Original Assignee: Cantaloupe Systems Incorporated (Cantaloupe, Inc.)
• Inventors: Chu, Eric Matthew, Cheng, Fred, Arora, Mandeep Singh, Beaudoin, Amedee Louis, Agrawal, Anant
• Primary Examiner(s): Crawford; Gene
• Assistant Examiner(s): COLLINS, MICHAEL
• Application Number:
  US11/096,889
• Time in Patent Office: 2,154 Days
• Field of Search: 700231-244, 705/28, 705/9, 235375-378, 701/200, 701/202
• US Class Current: 700/241
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 10/1097 Task assignment
• CPC Class Codes: G07F 9/002 Vending machines being part of a centrally controlled network of vending machines
• CPC Class Codes: G07F 9/026 for alarm, monitoring and auditing in vending machines or means for indication, e.g. when empty

Abstract

Techniques are provided for calculating vending machines'"'"' service priorities and scheduling the vending machines for service taking into account a number of factors and thresholds (520). In some embodiments, the machines (110) are subdivided into subroutes (320). Each subroute has one or more machines, and at least one subroute has a plurality of machines. The vending machine service schedule is generated by selecting the highest priority subroute (410) and selecting the machines in that subroute (420). Other subroutes can be selected (430, 440) if there is time left in the Service Period.

Claims

1. A system-implemented method for scheduling service for a plurality of vending machines to select those vending machines which are to be serviced in a predefined service period, the system comprising hardwired and/or software programmed circuitry, the method comprising operations of:

(1) determining, by said circuitry, a service priority indicator of each of a plurality of vending machines;

(2) determining, by said circuitry, a scheduling priority for each of a plurality of subroutes, each subroute being a set of one or more vending machines, at least one of the subroutes comprising a plurality of vending machines separated by driving times, wherein determining the scheduling priority of each subroute comprises adding, by said circuitry, the service priority indicators of the subroute'"'"'s plural vending machines and determining the scheduling priority as a function of a sum of the service priority indicators of the subroute'"'"'s vending machines;

(3) selecting, by said circuitry, a subroute S1 for service by using the scheduling priorities, the subroute S1 being one of the plurality of the subroutes;

(4) selecting, by said circuitry, one or more vending machines for service in the subroute S1 in said service period;

wherein each vending machine which is not selected is deselected for service in said service period.

2. The method of claim 1 wherein the service priority for at least one of the plurality of vending machines is determined by said circuitry using an estimate E1 defining an estimated time until a “

need-service time”

which is a time when the vending machine will need-service, wherein the at least one of the vending machines comprises one or more product containers, the method comprising generating, by said circuitry, the estimate E1 by using one or more predefined service threshold parameters which define one or more of;

(a) a threshold Th1 for a number of the product containers satisfying a condition C1 which is a condition that an amount of a product in the container is at most a predefined alert level for the container;

(b) a threshold Th2 for a number of the products vended by the at least one of the vending machines that satisfy a condition C2 which is a condition that an amount of the product in the vending machine is at most a predefined alert level for the product;

(c) a required service interval which is maximum time that the machine is to be allowed to operate without service;

(d) a threshold for an amount of money in the vending machine.

3. The method of claim 2 wherein the one or more service threshold parameters comprise a first service threshold parameter which defines the threshold for the number of the machine'"'"'s product containers satisfying the condition C1, wherein if a group of containers carries the same product, then only one container in the group is taken into account by said circuitry in generating the estimate E1.

4. The method of claim 3 wherein said one container in the group is a container that carries a maximum amount of the product among the containers in the group.

5. The method of claim 2 wherein the one or more service threshold parameters comprise a first service threshold parameter which defines the threshold Th1 or the threshold Th2;

and

wherein generating the estimate E1 comprises;

(1) said circuitry determining, for each of a first plurality of the product containers or products, a corresponding value t1 which defines an estimated time until (i) the container will satisfy the condition C1 for the container'"'"'s alert level or (ii) the product will satisfy the condition C2 for the product'"'"'s alert level; and

(2) for said first plurality of the containers or products, said circuitry determining a container or product which has an order corresponding to the threshold Th1 or Th2 in an ordering in which the containers or products are ordered by their increasing values t1;

wherein the estimate E1 is generated by said circuitry as the value t1 corresponding to the container or product determined in operation (2).

6. The method of claim 5 wherein said first plurality of containers or products is a plurality of containers which comprises, for each group of the containers that carry the same product, only a container that carries the maximum amount of said product.

7. The method of claim 1 wherein in the operation (1), each the vending machine'"'"'s service priority indicator is determined by said circuitry using an estimate E1 defining an estimated time until a “

need-service time”

which is a time when the vending machine will need-service, and the method further comprises said circuitry generating the estimate E1 for each vending machine.

8. The method of claim 7 wherein each vending machine comprises a plurality of product containers, and each vending machine'"'"'s estimate E1 is generated by said circuitry using one or more predefined service threshold parameters which define one or more of:

(a) a threshold Th1 for a number of the product containers satisfying a condition C1 which is a condition that an amount of a product in the container is at most a predefined alert level for the container;

(b) a threshold Th2 for a number of the products vended by the vending machine that satisfy a condition C2 which is a condition that an amount of the product in the vending machine is at most a predefined alert level for the product;

wherein the method further comprises said circuitry generating, for each vending machine, a corresponding estimate E2 with reference to (i) a number of the vending machine'"'"'s containers that will satisfy the condition C1 at the need-service time defined by the corresponding estimate E1, or (ii) a number of the vending machine'"'"'s products that will satisfy the condition C2 at the need-service time defined by the corresponding estimate E1;

wherein for each vending machine, its service priority indicator is also a function of the corresponding estimate E2.

9. The method of claim 8 wherein the estimate E2 is an estimate of the number of the vending machine'"'"'s containers that will satisfy the condition C1 at the need-service time defined by the corresponding estimate E1, wherein if a group of containers carries the same product, then only one container in the group is taken into account in calculating the estimate E2.

10. The method of claim 8 wherein the service priority indicator is generated by said circuitry as a function which increases in E1 and decreases in E2, or decreases in E1 and increases in E2.

11. The method of claim 10 wherein the service priority indicator is a ratio F1/F2, wherein one of F1 and F2 is a predefined linear function of E2^P, wherein the other one of F1 and F2 is a predefined linear function of E1^Q, and P is less than Q.

12. The method of claim 11 wherein P=0.5 and Q=1.75.

13. The method of claim 1 further comprising, after selecting the vending machines, said circuitry selecting another subroute S2 which is one of the plurality of the subroutes, and said circuitry selecting one or more vending machines for service from the subroute S2.

14. The method of claim 1 wherein the service is to be performed in a predefined service period.

15. The method of claim 14 wherein in the operation (4), the vending machine selection is based on the service priority indicators and on whether or not a vending machine satisfies a condition Cond1 which is a condition that the service period precedes the vending machine'"'"'s need-service time defined by the corresponding estimate E1 by more than a predefined amount;

wherein any vending machine have a lower priority for being selected if the vending machine satisfies the condition Cond1.

16. The method of claim 14 wherein the service period is insufficient for servicing all of the vending machines.

17. The method of claim 14 wherein the subroute S1 comprises a plurality of vending machines whose service priority indicators are used by said circuitry to select one or more vending machines in the operation (4).

18. The method of claim 1 wherein the subroutes are predefined before the operations (2)-(4).

19. The method of claim 1 wherein the subroute S1 comprises vending machines separated by driving times.

20. The method of claim 13 wherein each of the subroutes S1 and S2 comprises vending machines separated by driving times.

33. A manufacture operable to perform the method of claim 1.

34. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 1.

35. The manufacture of claim 34 further comprising a computer-readable data structure for use in scheduling service for the plurality of vending machine subroutes such that the service is scheduled for each of a plurality of service periods and in each service period one or more subroutes are to be serviced, and in each service period in which more than one subroutes are serviced the subroutes are to be serviced in sequence one after another, each subroute being a set of one or more vending machines and the vending machines are to be serviced in the order of their respective subroutes in each said sequence, the data structure comprising:

a subroute identifier which identifies a subroute S1; and

an indicator specifying whether or not, in each of the service periods, the subroute S1 can be serviced after another subroute.

36. The manufacture of claim 35 wherein said indicator comprises a list of one or more subroutes such that the subroute S1 can be serviced after any subroute S2 in the list in each of the service periods.

37. The manufacture of claim 35 wherein said indicator specifies one of the following three options:

Option 1;

in each of the service periods, the subroute S1 cannot be serviced after any other subroute, and can only be serviced as the first serviced subroute;

Option 2;

in each of the service periods, the subroute S1 can be the first serviced subroute and can also be serviced after another subroute in the;

Option 3;

in each of the service periods, the subroute S1 cannot be serviced as the first serviced subroute and can only be serviced after another subroute.

38. A network transmission method comprising transmitting, over a network, a computer-readable data structure as recited in claim 35.

39. A manufacture operable to perform the method of claim 1.

40. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 1.

41. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 1.

42. A manufacture operable to perform the method of claim 7.

43. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 7.

44. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 7.

54. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 1.

61. A manufacture operable to perform the method of claim 13.

62. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 13.

63. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 13.

64. A manufacture operable to perform the method of claim 19.

65. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 19.

66. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 19.

67. A manufacture operable to perform the method of claim 20.

68. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 20.

69. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 20.

21. A system-implemented method for selecting vending machines for being serviced in a predefined service period, the system comprising hardwired and/or software programmed circuitry, the method comprising operations of:

(1) determining, by said circuitry, a scheduling priority for each of a plurality of predefined subroutes, each subroute being a set of one or more vending machines, at least one of the subroutes comprising a plurality of vending machines separated by driving times, wherein for at least the one of the subroutes comprising the plurality of vending machines, the scheduling priority incorporates information on states of more than one of the subroute'"'"'s vending machines;

(2) said circuitry using the scheduling priorities to select one of the predefined subroutes for being serviced in the service period;

(3) said circuitry selecting one or more vending machines in the subroute selected in the operation (2) for being serviced in the service period;

(4) said circuitry repeating the operations (2), (3) as long as a service schedule for the service period is not full and there is a non-selected vending machine selectable for service in the operation (3), to select a new subroute in each iteration of the operation (2);

wherein at least two different iterations of the operation (2) result in selections of subroutes with respective two different scheduling priorities, and wherein less than all of the vending machines are selected by said circuitry for being serviced in the service period.

22. The method of claim 21 further comprising said circuitry obtaining data placing a restriction on an order in which the subroutes can be serviced in the service period, wherein:

the subroutes are scheduled by said circuitry to be serviced in an order of being selected in the operation (2); and

each subsequent iteration of the operation (2) selects a subroute having the highest scheduling priority among the unselected subroutes not restricted by said restriction from being serviced after the selected subroutes in the service period.

23. The method of claim 21 further comprising said circuitry obtaining data placing a restriction on an order in which the subroutes can be serviced in the service period, wherein:

the subroutes are scheduled by said circuitry to be serviced in an order of being selected in the operation (2); and

the first iteration of the operation (2) selects a subroute having the highest scheduling priority among the subroutes which are allowed by said data to be scheduled as the first to be serviced in the service period.

24. The method of claim 21 wherein in the operation (1), the scheduling priority for each subroute is determined by said circuitry as a decreasing function of each “

need-service time”

in the subroute, wherein each need-service time is associated with one of the subroute'"'"'s vending machines and is an estimated time until the associated vending machine will need service.

25. The method of claim 24 wherein in the operation (3), the vending machine has a lower priority for being selected if the service period precedes the vending machine'"'"'s need-service time by more than a predefined amount.

26. The method of claim 21 wherein the vending machines are located at a plurality of locations, and at least one location has more than one vending machines, and wherein selecting one or more vending machines for being serviced in the service period comprises:

said circuitry selecting vending machines according to one or more first selection rules for selecting and deselecting the vending machines;

for at least one location L1 comprising a vending machine VM1 selected by said circuitry according to the one or more selection rules and also comprising a vending machine VM2 deselected by said circuitry according to the one or more selection rules, said circuitry determining if one or more second selection rules apply to the machine VM2, and said circuitry selecting the machine VM2 if the one or more second selection rules apply.

27. The method of claim 26 wherein determining if the one or more second selection rules apply comprises said circuitry generating an estimate defining a time until an earliest time LT1 when any one of the vending machines at the location L1 will need service if all of the vending machines at the location L1 are serviced in the service period;

wherein the one or more second selection rules comprise a rule that the estimated need-service time of the vending machine VM2 be earlier than the time LT1.

28. The method of claim 26 wherein the one or more second selection rules comprise a rule that an amount of cash in the vending machine be at least a predefined threshold.

29. The method of claim 28 wherein the one or more second selection rules comprise a rule that a predefined required-service-interval for the machine expire on or before the service period.

30. The method of claim 21 wherein in the operation (1), each subroute'"'"'s scheduling priority is computed by said circuitry as a function of a sum of the subroute'"'"'s plural vending machines'"'"' service priority indicators.

31. The method of claim 21 wherein at least one subroute selected in the operations (2)-(4) comprises vending machines separated by driving times.

32. The method of claim 21 wherein the service schedule becomes full while there is still a non-selected vending machine selectable for service.

45. A manufacture operable to perform the method of claim 25.

46. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 25.

47. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 25.

48. A manufacture operable to perform the method of claim 26.

49. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 26.

50. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 26.

51. A manufacture operable to perform the method of claim 21.

52. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 21.

53. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 21.

55. A manufacture operable to perform the method of claim 22.

56. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 22.

57. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 22.

58. A manufacture operable to perform the method of claim 23.

59. A manufacture comprising a computer readable data medium comprising one or more computer instructions operable to cause a computer system to perform the method of claim 23.

60. A network transmission method comprising transmitting, over a network, a computer program operable to cause a computer system to perform the method of claim 23.