0

I've been thinking about how to do this for hours but am stuck.

I have a matrix A, with arrival times of customers, and a matrix D, with departure times of customers. E.g. a time in the arrival matrix means one customer arrived at that time, and a time in the departure matrix means one customer departed.

I am trying to plot a time series of the number of customers in the store from t=1..800 at intervals of 1. However, the arrival and departure times of the customers are determined by random variables, and this is a simulation that runs with the timestep increasing at random intervals, so I'm finding it hard to store the number of customers at given time intervals in the simulation itself.

I think there must be a way to fill out a matrix N with the number of customers at evenly spaced time intervals given the arrival and departure time matrices, but I can't for the life of me think of what it is. Can someone please point me in the right direction?

L. Wang
  • 3
  • 1
  • https://stackoverflow.com/questions/45972684/get-a-list-of-overlapping-time-ranges-from-a-set-of-appointments/45973161#45973161 – MBo Oct 31 '17 at 20:51
  • Thank you for the reply. I'm still confused about iterating through the matrix of arrival / departure times - I am not looking for overlap, but rather how to figure out the number of customers in the store at any given time. – L. Wang Oct 31 '17 at 21:12
  • Is there some reason you want to only plot at unit time ticks rather than plotting all of the queue length values when they occurred? The latter is actually more interesting. – pjs Oct 31 '17 at 22:10
  • @Lawrence Wang But `Counter` value - is the number of customers in the store at any given time – MBo Nov 01 '17 at 00:36

1 Answers1

1

Arrivals and departures are "events", and your arrays contain the times of those events. The basic logic is to find the time of the next event and do the updates associated with that event. For arrivals, queue length is incremented. For departures, the queue length is decremented. The following is a rather brute-force implementation (Python3 since you didn't specify) of that idea which prints out the time and the queue length whenever it changes:

a = [1.1, 2.9, 5.1, 6.5]
d = [3.5, 5.2, 7.2, 8.0]

queue = 0
a_index = 0
d_index = 0
print(0, ':', queue)

while a_index < len(a) and d_index < len(d):
    if a[a_index] < d[d_index]:  # did an arrival come first?
        queue += 1
        print(a[a_index], ':', queue)
        a_index += 1
    else:
        queue -= 1
        print(d[d_index], ':', queue)
        d_index += 1

# ran out of elements in one of the arrays,
# iterate through remainder of the other

while a_index < len(a):
    queue += 1
    print(a[a_index], ':', queue)
    a_index += 1

while d_index < len(d):
    queue -= 1
    print(d[d_index], ':', queue)
    d_index += 1

If you want to print only at integer times, set those up as events as well:

a = [1.1, 2.9, 5.1, 6.5]
d = [3.5, 5.2, 7.2, 8.0]

queue = 0
a_index = 0
d_index = 0
print_time = 1
max_time = 10
print(0, ':', queue)

while a_index < len(a) and d_index < len(d):
    if a[a_index] < d[d_index] and a[a_index] <= print_time:
        queue += 1
        a_index += 1
    elif d[d_index] <= print_time:
        queue -= 1
        d_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while a_index < len(a):
    if a[a_index] <= print_time:
        queue += 1
        a_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while d_index < len(d):
    if d[d_index] <= print_time:
        queue -= 1
        d_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while print_time <= max_time:
    print(print_time, ':', queue)
    print_time += 1

These could undoubtedly be tightened up, but they convey the approach.

If you had more than this small number of events, a better organizing principle would be to place the events in a priority queue, ordered by time of occurrence, then pull them off one-by-one and dispatch to the appropriate state transition logic based on which event type occurred. You can find the logic of this approach described in this paper. The paper implements the ideas in Java, but a Python3 implementation and a demo queueing model are available here.

pjs
  • 18,696
  • 4
  • 27
  • 56