[bp-users]Re: Vehicle Scheduling

[Neng-Fa Zhou]

Hi, you can find below a scheduler for a toy problem that displays visual
solutions. It is a toy problem and only non-overlap constraints are
involved. You also have non-overlap constraints such as "a truck cannot be
assigned to two missions at a time" and "no two trucks can be assgined to
deliver a box", but you need to consider other types of constraints as well.
I hope the attached program can serve as a good starting point for you.

Best regards,
Neng-Fa Zhou
============================================================
/* (C) Afany Software, all rights reserved.
Problem description: Four roomates named Algy, Bertie, Charlie, and Digby
are subscribing to four newspapers:
Financial times, Guardian, Daily express, and Sun. Each person has different
interests and spend different
amounts of time reading the newspapers. The following gives the amounts of
time each person spend on each newspaper:

    Person/Newspaper/Minutes
    ================================================================
    Person || Financial times  | Guardian | Daily express | Sun
    ----------------------------------------------------------------
    Algy   ||     60          |   30     |      2        |  5
    ----------------------------------------------------------------
    Bertie ||     75          |    3     |     15        | 10
    ----------------------------------------------------------------
    Charlie||      5          |   15     |     10        | 30
    ----------------------------------------------------------------
    Digby  ||     90          |    1     |      1        |  1
    ================================================================
Algy gets up at 7:00, Bertie gets up at 7:15, Charlie gets up at 7:15, and
Digby gets up at 8:00. Nobody can
read more than one newspaper at a time and at any time a newspaper can be
read by only one person.
Schedule the newspapers such that the four persons finish the newspapers at
an ealiest possible time.
*/
go:-
    Algy=person(algy,0,
  60,Algy_F,30,Algy_G,2,Algy_E,5,Algy_S),
    Bertie=person(bertie,15,
    75,Bertie_F,3,Bertie_G,15,Bertie_E,10,Bertie_S),
    Charlie=person(charlie,15,
     5,Charlie_F,15,Charlie_G,10,Charlie_E,30,Charlie_S),
    Digby=person(digby,60,
   90,Digby_F,1,Digby_G,1,Digby_E,1,Digby_S),
    %
    tasksNotOverlap([Algy,Bertie,Charlie,Digby], EndTimes,Vars),
    %
    intervalsNotOverlap([60,Algy_F,75,Bertie_F,5,Charlie_F,90,Digby_F]),
    intervalsNotOverlap([30,Algy_G,3,Bertie_G,15,Charlie_G,1,Digby_G]),
    intervalsNotOverlap([2,Algy_E,15,Bertie_E,10,Charlie_E,1,Digby_E]),
    intervalsNotOverlap([5,Algy_S,10,Bertie_S,30,Charlie_S,1,Digby_S]),
    max(EndTimes) #= EndTime,

%    fd_minimize(labeling(Vars),EndTime),
    labeling(Vars),
    visualizeSol([Algy,Bertie,Charlie,Digby]).

tasksNotOverlap([],EndTimes,Vars):-EndTimes=[],Vars=[].
tasksNotOverlap([person(Name,T0,DF,TF,DG,TG,DE,TE,DS,TS)|Ps],EndTimes,Vars):
-
    TF#>=T0,TG#>=T0,TE#>=T0,TS#>=T0,
    intervalsNotOverlap([DF,TF,DG,TG,DE,TE,DS,TS]),
    Vars=[TF,TG,TE,TS|Vars1],
    EF #= DF+TF,
    EG #= DG+TG,
    EE #= DE+TE,
    ES #= DS+TS,
    EndTimes=[EF,EG,EE,ES|EndTimes1],
    tasksNotOverlap(Ps,EndTimes1,Vars1).

intervalsNotOverlap([]).
intervalsNotOverlap([D,T|Is]):-
    intervalsNotOverlap(D,T,Is),
    intervalsNotOverlap(Is).

intervalsNotOverlap(_D,_T,[]).
intervalsNotOverlap(D,T,[D1,T1|Is]):-
    (D+T #=< T1 #\/ D1+T1 #=< T),
    intervalsNotOverlap(D,T,Is).

visualizeSol([Algy,Bertie,Charlie,Digby]):-
    cgWindow(Win),Win^title#="Newspaper Scheduler", Win^topMargin #= 40,
Win^leftMargin #= 10,
    Win^width #= 800,
    handleClose(Win),
    Labs=[Algy_l,Bertie_l,Charlie_l,Digby_l],
    cgLabel(Labs,["Algy","Bertie","Charlie","Digby"]),
    cgTable([[Algy_l],[Bertie_l],[Charlie_l],[Digby_l]],0,5),
    cgSame(Labs,size),
    cgSame(Labs,fontStyle,bold),
    cgSame(Labs,fontSize,16),
    cgSame(Labs,window,Win),
    cgShow(Labs),
    visulizePerson(Win,Algy_l,Algy),
    visulizePerson(Win,Bertie_l,Bertie),
    visulizePerson(Win,Charlie_l,Charlie),
    visulizePerson(Win,Digby_l,Digby).

visulizePerson(Win,Lab,person(Name,T0,DF,TF,DG,TG,DE,TE,DS,TS)):-
    cgRectangle([RF,RG,RE,RS]),
    constrainNewspaper(RF,Lab,TF,DF,black),
    constrainNewspaper(RG,Lab,TG,DG,blue),
    constrainNewspaper(RE,Lab,TE,DE,green),
    constrainNewspaper(RS,Lab,TS,DS,red),
    cgSame([RF,RG,RE,RS],window,Win),
    cgShow([RF,RG,RE,RS]).

constrainNewspaper(R,Lab,T,D,Color):-
    R^x #= Lab^rightX+T*3,
    R^y #= Lab^y,
    R^height #= Lab^height,
    R^width #= D*3,
    R^color #= Color.

handleClose(Win),{windowClosing(Win)} => halt.
============================================================================
==========
>
> I have a vehicle scheduling problem I would like to solve. I have been
> doing research regarding Logic and Constraint Programming and it seem
> like the way to go. The problem involves multiple orders received by a
> centraql depot with x number of vehicles. Based on the orders, the
> system must decide which vehicles to use, which vendors to pick the
> goods up from and in which sequence to deliver to the customers.
> Obviously the capacity of vehicles and other resources (i.e. drivers)
> have to be considered. I would appreciate any help regarding this.
> Regards,
>
> Myles Rennie
> South Africa
>
> _______________________________________________
> bp-users mailing list
> bp-users@lists.probp.com
> http://lists.probp.com/mailman/listinfo/bp-users
>