Thanks a lot for your time and reply. Yes, I was using an older version of the CPLEX and I ran the model in the latest version. The model produced a solution similar to yours.
However, the solution produced (Optimal value 100) is inaccurate. When I checked the values of decision variable K, I can see that the service #4 has been assigned twice. I cannot figure out why it is happening.
Is this error due the way I have written the code or due to some missing constraints ?
Original Message:
Sent: Mon November 14, 2022 03:28 AM
From: Philippe Refalo
Subject: Solving a Pickup and delivery problem
Are you using an old version of OPL ?
I ran the .mod and .dat provided with the latest CPLEX Optimization Studio (22.1) and it produces a solution (see below)
You maybe hit a bug that has been fixed since.
Philippe
Version identifier: 22.1.0.0 | 2022-02-22 | d27c09886 (dirty)
Legacy callback pi
Tried aggregator 3 times.
MIP Presolve eliminated 12 rows and 16 columns.
MIP Presolve added 1 rows and 1 columns.
Aggregator did 14 substitutions.
Reduced MIP has 66 rows, 100 columns, and 248 nonzeros.
Reduced MIP has 98 binaries, 2 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.63 ticks)
Found incumbent of value 150.000000 after 0.00 sec. (0.68 ticks)
Probing time = 0.00 sec. (0.06 ticks)
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve eliminated 1 rows and 4 columns.
Reduced MIP has 65 rows, 96 columns, and 244 nonzeros.
Reduced MIP has 96 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.20 ticks)
Probing time = 0.00 sec. (0.06 ticks)
Clique table members: 93.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.00 sec. (0.16 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 150.0000 0.0000 100.00%
* 0 0 integral 0 100.0000 100.0000 27 0.00%
Elapsed time = 0.00 sec. (2.28 ticks, tree = 0.00 MB, solutions = 2)
Root node processing (before b&c):
Real time = 0.00 sec. (2.29 ticks)
Parallel b&c, 12 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.00 sec. (2.29 ticks)
------------------------------
Philippe Refalo
IBM ILOG CP Optimizer
Original Message:
Sent: Thu November 10, 2022 12:40 PM
From: a vaikk
Subject: Solving a Pickup and delivery problem
Hi all,
I am relatively new to IBM-Cplex and I am trying to solve a pickup and delivery problem. The idea is to create a path for a request from an origin to a destination using an available set of services with a minimal cost.
Currently, my set of services and requests looks like this (<s.id,s.Origin,S.Destination,s.Cost>)
services = {
<1, 10, 3, 200>,
<2, 10, 5,100>,
<3, 1, 5, 100>,
<4, 5, 3, 50>
}
Request = <requestID, requestOrigin, requestDest>
Request = {1,10,3}
And an ideal solution would be < 3,1,5,100> <4,5,3,50> with a total cost of 150
However, I am not able find a solution since there is an error in my code and I am not able to identify it. I'd really appreciate if someone can take a look at it and guide me through out.
I will attach the mod file and the dat file below.
The code is :
//sets of service and requests
tuple service{
key int sID; //#id of service
key int o; //origin of service
key int d; //destination of service
key int cost; //cost of using service
}
tuple request{
key int rID; //#id of request
key int rO; //origin of a request
key int rD; //destination of a request
}
//list of services
{service} services=...;
//list of requests
{request} requests=...;
//total nodes(terminals)
sorted {int} nodes = {i.o| i in services} union {i.d|i in services};
//decision variables
//obj1 = Monetary Cost
dvar int obj1;
//1 if a service s is used between node i and j
dvar boolean k[services][nodes][nodes];
//1 if a service s is used to transport request r between node i and j
dvar boolean y[services][requests][nodes][nodes];
minimize obj1;
subject to{
//Total Cost
obj1==sum(s in services, i,j in nodes)k[s][i][j]*s.cost;
//Each vehicle may use atmost 1 service from its origin Depot
forall(s in services)
vehicleOrigin:
sum(j in nodes)k[s][s.o][j]<=1;
//if used, the vehicle must reach the destination depot
forall(s in services)
vehicleDestination:
sum(j in nodes)k[s][s.o][j] == sum(j in nodes)k[s][j][s.d];
//flow conservation of the vehicles
forall(s in services, i in nodes:i!=s.o&&i!=s.d)
vehicleFlow:
sum(j in nodes)k[s][i][j] == sum(j in nodes)k[s][j][i] ;
//all orders must be picked up from the origin
forall(r in requests)
requestOrigin:
sum(s in services, j in nodes)y[s][r][r.rO][j] == 1;
//all orders must reach the destination
forall(r in requests)
requestDestination:
sum(s in services, j in nodes)y[s][r][j][r.rD] == 1;
//flow conservation of requests
forall(r in requests, s in services, i in nodes : i!=r.rO && i!= r.rD)
requestFlow:
sum(j in nodes)y[s][r][i][j] == sum(j in nodes)y[s][r][j][i];
//enforce vehicle flow if there is some request flow between i and j
forall(r in requests, s in services, i ,j in nodes)
YandKconst:
y[s][r][i][j] <= k[s][i][j];
}
Thanks a lot for your time :)
------------------------------
------------------------------
#DecisionOptimization