配送計画問題（C言語）

[asami_usuda777]

現在，大学で配送計画問題を研究しています．
そこで，配送ルートを列挙するプログラムをC言語で書くように教授から指導がありました．
現在研究を行っている配送問題は少し特殊で，集積所1→配送先1→配送先2→集積所2→集積所3→配送先3などのように注文の組み合わせが決まっています．
配送順が記された表を参照し，配送ルートを列挙するプログラムまではできています．
しかし，ルートを列挙しただけで，配送時間を考慮するプログラムはどのように書けばよいのか分かりません．
配送先と集積所にはそれぞれ積み込み，積み降ろし時間が約15分程度かかり，積み込み時間も9:00〜10:00まで，12:00（ピンポイントに指定）などで，配送先に届けなければならない時間も同様に指定があります．
さらに配送にかかる時間も考慮しなければなりません．
これらの時間を考慮し，それが最適なルートになるものを列挙したいと考えています．
今作ったコードの実行結果はこのようになっています．
2次元の配列を用意し，dが集積所，cが配送先を指しています．
1が通過可能で0が通過不可能です．

ソースコード

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

int D;
int C;

void setNode(int*, int*, int, int, int**);
void checkdc(int, int*, int**);
void deletedc(int, int* checkRoute, int**);
void printRoute(int*);

int main(int argc, char** argv)
{
D = atoi(argv[1]);
C = atoi(argv[2]);

int* route = new int[D + C];
int* checkRoute = new int[D + C];
int** dc = new int*[D];
for (int i = 0; i < D; i++){
dc = new int[C];
}

dc[0][0] = 1; dc[0][1] = 0; // dc[0][2] = 0;
dc[1][0] = 0; dc[1][1] = 1; // dc[1][2] = 1;
// dc[2][0] = 0; dc[2][1] = 1; dc[2][2] = 0;
// dc[3][0] = 0; dc[3][1] = 1; dc[3][2] = 1;

clock_t s, e;

for (int i = 0; i < D + C; i++) {
route = -1;
}
for (int i = 0; i < D; i++) {
checkRoute = 0;
}
for (int i = D; i < D + C; i++) {
checkRoute = -1;
}

s = clock();
for (int i = 0; i < D; i++) {

setNode(route, checkRoute, i, 0, dc);
checkRoute = 0;
route = -1;

}
e = clock();
cerr << "Comp Time : " << (double)(e - s)/CLOCKS_PER_SEC << endl;
delete [] route;
delete [] checkRoute;

return 0;
}

void setNode(int* route, int* checkRoute, int Node, int num, int** dc)
{
route[num] = Node;
checkRoute[Node] = 1;
if (Node < D) {
checkdc(Node, checkRoute, dc);
}
for (int i = 0; i < D + C; i++) {
if (checkRoute == 0) {
setNode(route, checkRoute, i, num + 1, dc);
checkRoute = 0;
route[num + 1] = -1;
if (i < D) {
deletedc(i, checkRoute, dc);
}
}
}

if (num + 1 == D + C) {
printRoute(route);
}

return;
}

void printRoute(int* route)
{
static int numRoute;

cout.width(3);
cout << ++numRoute << ": ";

for (int i = 0; i < D + C; i++) {
if (route < D) {
cout << "D" << route;
} else {
cout << "C" << route[i] - D;
}
if (i < D + C - 1) {
cout << " - ";
}
}
cout << endl;

return;
}

void checkdc(int Node,int* checkRoute,int** dc)
{
for (int i = 0; i < C; i++) {
if (dc[Node][i] == 1){
for (int j = 0; j < D; j++){
if (dc[j][i] == 1 && dc[j][i] != checkRoute[j]){
break;
}
if (j == D - 1){
checkRoute[D + i] = 0;
}
}
}
}
}

void deletedc(int num,int* checkRoute,int** dc)
{
for (int i = 0; i < C; i++) {
if (dc[num][i] == 1){
checkRoute[D + i] = -1;
}
}
}

実行結果

bash-3.2$ ./1112 2 2
1: D0 - D1 - C0 - C1
2: D0 - D1 - C1 - C0
3: D0 - C0 - D1 - C1
4: D1 - D0 - C0 - C1
5: D1 - D0 - C1 - C0
6: D1 - C1 - D0 - C0
Comp Time : 8.3e-05

これらのルートに時間的な制約を加えたコードをご教授願いたいです．
宜しくお願いします．

[asami_usuda777]

すみません．コードです．

コード:

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

int D;
int C;

void setNode(int*, int*, int, int, int**);
void checkdc(int, int*, int**);
void deletedc(int, int* checkRoute, int**);
void printRoute(int*); 

int main(int argc, char** argv)
{
  D = atoi(argv[1]);
  C = atoi(argv[2]);

  int* route = new int[D + C];
  int* checkRoute =  new int[D + C];
  int** dc = new int*[D];
  for (int i = 0; i < D; i++){
    dc[i] = new int[C];
  }
  
  dc[0][0] = 1;  dc[0][1] = 0;  // dc[0][2] = 0;
  dc[1][0] = 0;  dc[1][1] = 1;  // dc[1][2] = 1;
  // dc[2][0] = 0;  dc[2][1] = 1;  dc[2][2] = 0;
  // dc[3][0] = 0;  dc[3][1] = 1;  dc[3][2] = 1;
  
  clock_t s, e; 

  for (int i = 0; i < D + C; i++) {
    route[i] = -1;
  }
  for (int i = 0; i < D; i++) { 
    checkRoute[i] = 0; 
  }
  for (int i = D; i < D + C; i++) { 
    checkRoute[i] = -1;
  }

  s = clock();
  for (int i = 0; i < D; i++) {

    setNode(route, checkRoute, i, 0, dc);
    checkRoute[i] = 0;
    route[i] = -1;

  }

  e = clock();
  cerr << "Comp Time : " << (double)(e - s)/CLOCKS_PER_SEC << endl;
  delete [] route;
  delete [] checkRoute;

  return 0;
}

void setNode(int* route, int* checkRoute, int Node, int num, int** dc)
{
  route[num] = Node;
  checkRoute[Node] = 1;
  if (Node < D) {
    checkdc(Node, checkRoute, dc);
  }
  for (int i = 0; i < D + C; i++) {
    if (checkRoute[i] == 0) {
      setNode(route, checkRoute, i, num + 1, dc);
      checkRoute[i] = 0;
      route[num + 1] = -1;
      if (i < D) {
	deletedc(i, checkRoute, dc);
      }
    }
  }

  if (num + 1  == D + C) {
    printRoute(route);
  }
  
  return;
}

void printRoute(int* route)
{
  static int numRoute;
  
  cout.width(3);
  cout << ++numRoute << ": ";

  for (int i = 0; i < D + C; i++) {
    if (route[i] < D) {
      cout << "D" << route[i];
    } else {
      cout << "C" << route[i] - D; 
    }
    if (i < D + C - 1) {
      cout << " - ";
    }
  }
  cout << endl;
  
  return;
}

void checkdc(int Node,int* checkRoute,int** dc)
{  
  for (int i = 0; i < C; i++) {
    if (dc[Node][i] == 1){
      for (int j = 0; j < D; j++){
	if (dc[j][i] == 1 && dc[j][i] != checkRoute[j]){
	  break;
	}
	if (j == D - 1){  
	  checkRoute[D + i] = 0;
	}
      }
    }
  }
}

void deletedc(int num,int* checkRoute,int** dc)
{
  for (int i = 0; i < C; i++) {
    if (dc[num][i] == 1){
      checkRoute[D + i] = -1;
    }
  }
}

[usao]

何をしたいのかよくわからないけど，取り得るルートを列挙できているのなら
それら個々のルートに関して，あなたが課す制約条件を満たしているか否か　を判定すればよいのでは？

オフトピック

まずもって　問題定義から不明瞭に思うのだけど．
制約条件を絶対に満たせない場合はどうすんの？とか．
（「配送計画問題」という言葉だけで，伝わる人には伝わるのか？？）
あと，変数の意味すら不明なコードをどさっと貼って，何の説明もなく
「何やってるのかは見る側で全て解読してくれ→その上でやりたいことも追加してくれ」
というスタンス(?)は　どうなのかなぁ……とか．

[asami_usuda777]

そうですね．．．すみません(ノД`)・゜・。

[usao]

別にそういう反応が欲しいわけではなくて，
そんなあいまいな投げ方ではなく，例えば問題の具体的なケースとかを決めた上で
・現コードの内容
・何で困ってるのか
くらいをちゃんと提示すればどうでしょうか，ということなのですけど…

オフトピック

大学の研究をこういう掲示板で訊いてやっても大丈夫なんでしょうか？
という話も　また別にあるかもしれませんが．

[みけCAT]

単純に最短経路で行って、指定された時間まで目的地で待機するのではダメなのですか？
実際に配送することを考えると、遠回りするよりその方が燃料や労力も無駄にならなくて良さそうに思えます。
（もちろん待機中はアイドリングストップをするとして）

ダメな場合、「最適」の評価基準を教えてください。