minimize/maximize \(\sum_{i=0}^{f(n)} G(x,n)\) s.t. \(n \ge 1\) and \(x\) in some feasible region

The decision variables are \(x\) (a vector) and \(x\) (a scalar).

How is this type of optimization problem classified?
Has it been studied? Any references?

Here is an example of how an unconstrained version of the problem arises:

"Optimizing capacity of buses, K, on a bus route"

  • The bus route is a loop. One point on the loop is designated the “bus station,” the only place passengers can get on the bus.
  • Passengers can get off the bus at any point on the bus route (other than the bus station).
  • By the time a bus returns to the bus station, all of its passengers will have gotten off.
  • Passengers arrive by a Poisson process with rate lambda (per hour).
  • A bus cannot take off from the bus station until it has K passengers on board.
  • There are N buses that operate on the one route. When a bus arrives at the bus station, it waits in line behind buses that are already there. It's a FIFO system where the first bus in line gets first K arriving passengers, and so on…
  • When a passenger arrives at the station, s/he gets on the first bus in line and waits until enough passengers have gotten on the bus to make a total of K passengers before the bus takes off. Passengers get on the bus in a FIFO manner as well.
  • The waiting time for a passenger is the length of time from when that passenger arrived at the bus station until a bus with that passenger on board takes off.
  • The waiting time for a bus is the length of time from when the bus arrives at the station until it has K passengers on board, at which point it takes off.
  • It is assumed that the “loading” of passengers takes zero time.
  • Also, it takes C(K) time for buses to travel the length of the bus route. This is a function of K because there is time lost for each passenger that is dropped off.

What is the expected waiting time for passengers? For buses?

The optimization aspect is as follows. Bus drivers want to make the most amount of money in an hour. The higher K is, the more money a bus driver makes per trip on the bus route, but the number of trips per hour goes down. There is a monetary cost (to bus drivers) for each minute that a passenger waits at the stop for a bus (as in loss of goodwill). So the objective function is dependent on both the expected waiting time of buses (which determines how much money buses make per hour) and the expected waiting time of passengers.

I was able to get an expression for the expected waiting time of buses and it is of the form:

E[Waiting time for a bus] = \(\sum_{j=0}^{KN} \frac{KN-j}{\lambda}\frac{(\lambda C(K))^j}{j!}e^{-\lambda C(K)}\)

E[Waiting time for a passenger] = ??

I have not been able to get an expression for the waiting time of passengers, but I suspect it will also have the upper bound of summation as some function of K.

asked 12 Oct '10, 01:30

archbishopmendel's gravatar image

archbishopme...
1112
accept rate: 0%

edited 06 Dec '13, 18:34

fbahr's gravatar image

fbahr ♦
4.6k716

Ah, Brings back memories from passanger buses in Transport Tycoon...

What is the expected waiting time for passengers? For buses?

Queueing theory would probably be the first thing to google here...

This little page should help you as well

As for your other questions it would probably be a bit easier to help you if your equations where readable(LateX syntax doesnt work here)...

(12 Oct '10, 06:57) Buxley

I was referring to the optimization problem, not the queueing problem. The optimization problem has a variable number of terms in the summation and this number, K, also shows up in the objective function.

(12 Oct '10, 07:46) archbishopme...

Without getting into the specifics of your problem, one general approach for tying the indices of a summation to a variable in an optimization model is to (a) bound the number of possible terms, (b) sum over every possible term and (c) multiply each term by a binary indicator variable that decides whether that term should be included or omitted. The binary variables are then tied to whatever was supposed to be controlling the summation by constraints. If the rest of the model is linear, the products of the summation terms with the binaries can be linearized by adding auxiliary variables and additional constraints (see, for instance, http://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html).

Another possibility might be to investigate constraint programming (CP) as an alternative to an optimization model. CP allows variables to serve as indices to sums and for that matter to other variables (e.g., x[y] where x is a variable array and y is a variable).

link

answered 12 Oct '10, 13:52

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

Thanks Paul. This looks promising. Only one detail is missing. Consider this problem: minimize F(1)+F(2)+F(3)+... Your approach works if we're only interested in finding k such that Sum{i in T} F(i) is optimal for some T subset of {1,2,3,...} with |T|=k, meaning the indices in T don’t have to be consecutive starting from 1 to k. A solution to the problem I posed is some k such that F(1)+F(2)+...+F(k) is optimal. Per your suggestion, if we let X(i) be the binary variable for the F(i) term, then we must also have constraints of the form: X(i) >=X(i+1). Thus if X(k) = 1, then X(i)=1 for all i<k.

(13 Oct '10, 05:52) archbishopme...
1

That's one approach. Another is to minimize z subject to constraints of the form z >= F(1) + ... + F(k) - M*(1-X(k)) where M is a sufficiently large parameter. (Maximization is handled similarly with the constraints reversed and the "big M" term added.

(13 Oct '10, 21:28) Paul Rubin ♦♦

I have to think about your second suggestion. Any thoughts on an expression for the expected waiting time for passengers? I could really use the help.

(14 Oct '10, 02:22) archbishopme...

The time between bus departures will have an Erlang distribution (http://en.wikipedia.org/wiki/Erlang_distribution#Waiting_times). It seems to me that the conditional distribution of the arrival times for the first K-1 passengers on the next bus, given the (Erlang) departure time, is uniform over the time interval between previous and next departure (but my memory of stochastic processes is itself stochastic). If I'm right, the mean waiting time would be 1/2 the mean interdeparture time for everyone except the last passenger to board (so (K-1)/(2K) times the Erlang mean).

(14 Oct '10, 13:42) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×79
×8

Asked: 12 Oct '10, 01:30

Seen: 7,274 times

Last updated: 06 Dec '13, 18:34

OR-Exchange! Your site for questions, answers, and announcements about operations research.