Handling multiple dimensions of arrays with speed
Have some rewrite rules applied, combinators used and helpers inlined while I think about your algorithmic question. And make Vendor a newtype.

minimalBasketPrice mP vD
  = nub
  . map vendorNbr
  . minimumOn (sum . map deliveryTime)
  . filter ((&lt;= mP) . sum . map itemPrice)
  . sequence
  . (map . filter) ((/= -1) . itemPrice)
  . transpose
  . zipWith3 (\x y -&gt; map (Vendor x y)) [0..] vD


This is the backpack problem and NP-hard. We won't be scaling well in the worst-case whatever we do, but we can do a little better by, for example, only keeping track of suffixes of vendor selections that can't be undercut in time and price at the same time:

newtype Candidate a = Candidate
  { vendors :: [Int]
  , time :: Int
  , price :: Int 
  }

minimalBasketPrice mP vD
  = nub . vendors . head
  . foldr (foo mP) [Candidate [] 0 0]
  . map (filter ((/= -1) . itemPrice))
  . transpose
  . zipWith3 (\x y -&gt; map (Vendor x y)) [0..] vD

foo :: Int -&gt; [Vendor] -&gt; [Candidate] -&gt; [Candidate]
foo mP choices
  = catMaybes . snd
  . mapAccumL bar (mP+1)
  . sortOn time
  . liftA2 addVendor choices

bar :: Int -&gt; Candidate -&gt; (Int, Maybe Candidate)
bar bestprice candidate = if price candidate &lt; bestprice
  then (price candidate, Just candidate)
  else (bestprice, Nothing)

addVendor (Vendor v t p) (Candidate vs ts ps) = Candidate (v:vs) (t+ts) (p+ps)