Classmates,

Attached you will find an updated version of the light timing problem and
the test.h file I used.

Laurie

--=====================_896836095==_
Content-Type: text/plain; charset="us-ascii"

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <stdio.h>

#include "test.h"

/* This program will calculate the total north-bound (NB) and south-bound (SB) delays
for two vehicle platoons traveling on an arterial.  The number of vehicles in the 
NB and SB platoons is variable and assumed to be given by a uniform distribution 
(within a prespecified range).  The number of vehicles in the NB platoon is 
independent of the number of vehicles in the SB platoon.

A neighborhood structure is defined such that the offset of one of the two cycles 
(selected with equal probability) will increase or decrease by one second (with 	
equal probability).

Note that the delay function is a "rough cut" model that will allow one to
optimize progression in BOTH the NB and SB directions when demand is variable.
In general, the total number of possible solutions for this problem is 
(CYCLELENGTH)^ a.nint.  As currently set up this will be 30^2 or 900 candidate theta's.
Using the mapping function, this corresponds to a value between 2 and 960.

In general, the objective function is bounded between zero and sum over all i 
intersections of 2*MAXNVEH*(CYCLETIME-greentime at intersection i).  
The term in the parenthesis represents the maximum amount of "red" time a vehicle 
can see at intersection i.  The term 2*MAXNVEH represents the maximum
number of vehicles that will travel on the arterial.For this problem, this expression 
is 2*15*(30-20 + 30-26) or 420.  

Finally, there may be many optimal solutions to this problem and a lot of noise.

*/


//Global constants used to define arrays and easily change problem parameters

const int MAXNINT = 5;          //max no of intersections in arterial + 2
const int CYCLELENGTH = 30;     //in seconds
const int MAXNVEH = 16;         //max no of vehicles in platoon per cycle length + 1
                                //(average is 15 per direction per cycle length)
                                //routine assumes uniform demand dist for EACH direct
                                //between 5 and 15, demands are indep in each direct
const int MEANNVEH = 10;        //mean number of vehicles in both NB and SB directions
const int PROGSPEED = 30;       //NB and SB progression speed in miles per hour
                                //assumed these are the same


// C++ classes and functions used to model the problem

class vehicle {
public:
	int time[MAXNINT];                //time of arrival (sec) at intersection i
	                                  //dept time of vehicle for time[0]; diff NB, SB ref
	int delay[MAXNINT];               //delay vehicle incurs at intersection i
	
	
	void init();                      //initialization of vehicle delays
	void timecalc(int, int, int);     //calculates time of arrival at downstream intersect
	     	                          //need to send curr intersect num, dept time from 
                                      //curr intersect, dist to next int
    void delaycalc(int, int, int);    //calcs delay at current intersect
                                      //send curr intersect no, intersect
                                      //offset, green time
};	



void vehicle::init() {
	for (int i = 0; i<MAXNINT; i++)
	{
		time[i]=0;
		delay[i]=0;
	}
};



void vehicle::timecalc(int intno, int depttime, int dist) {

	time[intno+1] = depttime + floor(dist/PROGSPEED*3600/5280);
};



void vehicle::delaycalc(int intno, int offset, int green) {
	
	int arrcompare;		 //arrival time of vehicle referenced to cycle length
	int greenend;        //end of green time referenced to cycle length

	arrcompare = time[intno] - floor(time[intno]/CYCLELENGTH)*CYCLELENGTH;

	if (arrcompare == 0)
		arrcompare = 30;

	greenend = green + offset - floor(((green+offset)/CYCLELENGTH)*CYCLELENGTH);

	if (offset <= arrcompare)
	{
		if ((greenend<arrcompare) && (greenend >offset))
			delay[intno] = CYCLELENGTH-arrcompare + offset;
		else 
			delay[intno] = 0;
	}


	else
	{
		if ((arrcompare<greenend) && (greenend < offset))
		     delay[intno] =0;
		else
			 delay[intno] = offset-arrcompare;
	}
};



class platoon {
public:
	int NBveh;	            //counter for number of vehicles in NB platoon
	int SBveh;              //counter for number of vehicles in SB platoon  
	vehicle NB[MAXNVEH];    //dept time from ref point 1 of each veh in NB platoon
	vehicle SB[MAXNVEH];    //dept time from ref point 2 of each veh in SB platoon

	void init();            //initialize platoon parameters (rand number in platoon)
	double totalNBdelay();	//computes total delay for NB platoon
	double totalSBdelay();	//computes total delay for SB platoon
};

 
   
void platoon::init() {

	/* This function initializes the parameters associated with
	   the vehicles in the platoon.  The number of vehicles in the
	   platoon is uniformly distributed between 5 and 15 for this
	   particular problem using a U(0,1) generated by rand() 
	*/

	


	NBveh = floor(MAXNVEH-1-2*(MAXNVEH-1-MEANNVEH)*(rand(2)));
	SBveh = floor(MAXNVEH-1-2*(MAXNVEH-1-MEANNVEH)*(rand(2)));


	//NOTE: time[0] for NB traffic is from ref. point 1
	//      time[0] for SB traffic is from ref. point 2

	for (int i=1; i<=NBveh; i++)
		NB[i].time[i-1] = 2*i;

	for (int j=1; j<=SBveh; j++)
		SB[j].time[j-1] = 2*j;
};



double platoon::totalNBdelay() {

	double delaytemp = 0.0;

	for (int i=1; i<=NBveh; i++)
	{
		for (int j=1; j<MAXNINT; j++)
		{
			delaytemp +=NB[i].delay[j];
		}
	}
	return delaytemp;
};



double platoon::totalSBdelay() {

	double delaytemp = 0;

	for (int i=1; i<=SBveh; i++)
	{
		for (int j=1; j<MAXNINT; j++) 
		{
			delaytemp +=SB[i].delay[j];

		}

	}

	return delaytemp;
};



class arterial {
public:
	int nint;               //number of intersections in arterial
	int dist[MAXNINT];      //distance (feet) intersection is from ref point 1
	int green[MAXNINT];     //amount of green on arterial for intersect i
	int offset[MAXNINT];    //beginning of green on arterial (sec) from ref point 1
                            //these are the decision variables mapped from theta
	void init(long);        //init of arterial parameters; send theta
};




void arterial::init(long theta2) {

	for (int i=1; i<MAXNINT; i++)
	{
		dist[i] = 0;
		offset[i] = CYCLELENGTH;
	}

	//mapping function is currently hard-wired for specific test problem
	offset[1] = floor(theta2/(31));
	offset[2] = theta2 - offset[1]*31;



	//NOTE: reference point 1 is 500 feet SB from intersection 1

	dist[1] = 500;
	dist[2] = 700;  //NOTE: 2 intersections	in this problem
                    //NOTE: last intersection + 500 is reference point for SB vehicles               
    green[1] = 20;	
	green[2] = 26;

};



 double f(long theta) {
	 
 /* This function returns a single random value from the signal
    timing test problem.  The function is written in C++ and includes
	class functions.  More details on specific steps are included 
	within the class functions.
*/


	 //variable declarations and initializations

	 arterial a;
	 a.nint = 2;           //two intersections for this problem
	 a.init(theta);
	 platoon p;
	 double delay = 0;     //records total arterial delay
	 
     for (int k=1; k<MAXNVEH; k++)
     {
          p.NB[k].init();
          p.SB[k].init();
     }

	 p.init();

	//calculate delay

	 for  (int j = 1; j<=a.nint; j++) 
	 {
		 for (int i=1; i<=p.NBveh-1; i++)
		 {
		   p.NB[i].timecalc(j, p.NB[i].time[j-1]+p.NB[i].delay[j-1], a.dist[j]);
           p.NB[i].delaycalc(j, a.offset[j], a.green[j]);
         }
	 }

     for  (int l = a.nint; l>=1; l--) 
	 {		  
		  for (k=1; k<=p.SBveh-1; k++)
          {					  
		   p.SB[k].timecalc(l, p.SB[k].time[l-1]+p.SB[k].delay[l-1], a.dist[l+1]-a.dist[l]);
           p.SB[k].delaycalc(l, a.offset[l], a.green[l]);
          }
	 }

	 delay = p.totalNBdelay() +p.totalSBdelay();

	return delay;

 }


 long neighbor(long theta) {

/* This function generates a candidate solution from the neighborhood of theta
   for the feasible region THETA[i] = [1,16,...CYCLELENGTH] for i = 1 to a.nint 
   in this case 2 intersections).  One of the cycles is randomly selected and
   then the offset is increased or decreased by one second using a wrapping 
   function.  The function is currently hardwired for two itersections.
*/

	 long offset1;
	 long offset2;
	 long newtheta;

	 offset1 = floor(theta/(CYCLELENGTH+1));
	 offset2 = theta - offset1*(CYCLELENGTH+1);

	 //input error check

	 if (offset1>CYCLELENGTH || offset1<1)
		 return -9999;

	 if (offset1>CYCLELENGTH || offset1<1)
		 return -9999;

	 double U1, U2;
	 long newoffset1;
	 long newoffset2;

	 newoffset1 = offset1;
	 newoffset2 = offset2;

	 U1 = rand(6);
	 U2 = rand(8);
	 
	 if ( U1 < 0.5)
		 newoffset1=offset1+1;
	 
	 else if (U1 >= 0.5)
		 newoffset1=offset1-1;

	 else if (U2 < 0.5)
		 newoffset2 = offset2+1;

	 else
		 newoffset2 = offset2-1;


	 //wrap if necessary
	 if (newoffset1 == CYCLELENGTH +1)
		newoffset1 = 1;

	 if (newoffset2 == CYCLELENGTH +1)
		 newoffset2 = 1;

	 if (newoffset1 == 0)
		 newoffset1 = CYCLELENGTH;

	 if (newoffset2 == 0)
		 newoffset2 = CYCLELENGTH;

	 //map function back to a long integer

	 newtheta = newoffset2 + newoffset1*31;


	 return newtheta;
	 
 } //end of neighbor function



 long initTheta() {

/* This function returns a starting solution for the timing test problem
   the solutions is randomly sampled from the feasible region
   THETA[i] = [1,16,...30] for i = 1 to a.nint (in this case 2 intersections)
   The function is generated directly using the mapping function. 
*/
      long theta;

	  theta = floor(rand(7)*29+1) + floor(rand(8)*29+1)*31;

      return theta;
}



//////////////////////////////////////////////////////////////////////////
//Random-Number Generator form Law and Kelton, p454
//Prime modulus multiplicative linear congruential generator
//Z[i]=(630360013 *Z[i-1]) (mod(pow2,31)-1), based on Marse and
//Roberts portable Fortran random-number generator UINRAN.  Multiple
//(100) streams are supported, with seeds spaced 100,000 apart.
//throughout, input argument "stream" must be an int giving the 
//desired stream number.  The header file rand.h must be included
// in the calling program (#include "rand.h") before using these 
// functions

//Usage: (Three functions)

//1. To obtain the next U(0,1) random number from stream "stream,"
//		execute
//			u = rand(stream);
//		where rand is a float function.  The float variable u will
//		contain  the next random number.
//
//2. To set the seed for stream "stream" to a desired value zset,
//		execute
//			randst(zset, stream);
//		where randst is a void function and szet must be a long set to
//		the desired seed, a number between 1 and 2147483646 (inclusive).
//		Default seeds for all 100 streams are given in the code.
//
//3. To get the current (most recently used)integer in the sequence
//	 being generated for stream "stream" into the long variable zget,
//		execute
//		  zget = randgt(stream)
//		where randgt is a long function



/* Generate the next random number. */
double rand(int stream)
{
    long zi, lowprd, hi31;

    zi     = zrng[stream];
    lowprd = (zi & 65535) * MULT1;
    hi31   = (zi >> 16) * MULT1 + (lowprd >> 16);
    zi     = ((lowprd & 65535) - MODLUS) +
             ((hi31 & 32767) << 16) + (hi31 >> 15);
    if (zi < 0) zi += MODLUS;
    lowprd = (zi & 65535) * MULT2;
    hi31   = (zi >> 16) * MULT2 + (lowprd >> 16);
    zi     = ((lowprd & 65535) - MODLUS) +
             ((hi31 & 32767) << 16) + (hi31 >> 15);
    if (zi < 0) zi += MODLUS;
    zrng[stream] = zi;
    return (( (double) (zi >> 7 | 1) + 1 )/ 16777216.0);
}

////////////////////////////////////////////////////////////////////////////////
//Set the current zrng for stream "stream" to zset
void randst (long zset, int stream)
{
	zrng[stream] = zset;
}
/////////////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////////
//Return the current zrng for stream "stream".

long randgt (int stream)
{
	return zrng[stream];
}
//////////////////////////////////////////////////////////////////////////////////


/*
//test to see if all functions work
void main(void)
{

long theta;

theta = initTheta();
cout <<theta<< endl;

theta = neighbor(theta);
cout <<theta<< endl;

cout <<f(theta)<<endl;

}

*/
--=====================_896836095==_
Content-Type: text/plain; charset="us-ascii"


// following is the header file for test1.cpp, test2.cpp, test3.cpp

#ifndef TEST_H
#define TEST_H

#include <math.h>
#include <limits.h>
#include <float.h>
#include <stdlib.h>
#include <iostream.h>



//Declarations
double f(long theta);
// this function returns a single random value from the
// quadratic test function of Nelson at point theta.
// it calls CalcNorm, a function to generate N(0,1)
// random variates via the inverse cdf method, by
// passing a U(0,1) generated by rand();

long neighbor(long theta);
// this routine generates a candidate solution from the neighborhood
// of theta for the feasible region THETA = [-100, -99, ..., 99, 100]
// by wrapping the feasible region.
// if a bad value is entered, the function returns -9999
// the value is shifted by 100 so as to be an index between 0 and 200

long initTheta(void);
// this function returns a starting solution for test function 1
// the solution is randomly generated from the feasible region
// THETA = [-100, -99, ..., 99, 100] but shifted by 100
// so as to be an index between 0 and 200

double CalcNorm(double U);
// Approximate inverse cdf for standard normal
// Based on vnorm in Bratley, Fox, and Schrage, p.339

//Law & Kelton generator p.454-6
double rand(int stream);
void randst(long zset, int stream);
long randgt(int stream);


//Definitions for L&K
// Define the constants 
#define MODLUS 2147483647
#define MULT1       24112
#define MULT2       26143

/* Set the default seeds for all 100 streams. */
static long zrng[] =
{         0,
 1973272912, 281629770,  20006270,1280689831,2096730329,1933576050,
  913566091, 246780520,1363774876, 604901985,1511192140,1259851944,
  824064364, 150493284, 242708531,  75253171,1964472944,1202299975,
  233217322,1911216000, 726370533, 403498145, 993232223,1103205531,
  762430696,1922803170,1385516923,  76271663, 413682397, 726466604,
  336157058,1432650381,1120463904, 595778810, 877722890,1046574445,
   68911991,2088367019, 748545416, 622401386,2122378830, 640690903,
 1774806513,2132545692,2079249579,  78130110, 852776735,1187867272,
 1351423507,1645973084,1997049139, 922510944,2045512870, 898585771,
  243649545,1004818771, 773686062, 403188473, 372279877,1901633463,
  498067494,2087759558, 493157915, 597104727,1530940798,1814496276,
  536444882,1663153658, 855503735,  67784357,1432404475, 619691088,
  119025595, 880802310, 176192644,1116780070, 277854671,1366580350,
 1142483975,2026948561,1053920743, 786262391,1792203830,1494667770,
 1923011392,1433700034,1244184613,1147297105, 539712780,1545929719,
  190641742,1645390429, 264907697, 620389253,1502074852, 927711160,
  364849192,2049576050, 638580085, 547070247 };

#endif


--=====================_896836095==_--